Hide
Problem E
Powers of 2
Powers of 2
Theta has been learning about powers of $2$ in school. She notices that some numbers when written out contain powers of $2$ in their digit representation: for instance, $12\, 560$ contains $256$ which is a power of $2$. She has been wondering how many such numbers there are.
Can you write a program that counts how many numbers contain a given power of $2$?
Input
The input consists of a single line with two integers $n$ and $e$ ($0 \le n \le 9 \cdot 10^{18}, 0 \le e \le 62$).
Output
Output a single integer that is equal to the number of distinct integers $k$ ($0 \le k \le n$) whose decimal representation contains the digits of $2^ e$ as a substring.
| Sample Input 1 | Sample Output 1 |
|---|---|
1000000 1 |
468559 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1000000 5 |
49401 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1000000 16 |
20 |
| Sample Input 4 | Sample Output 4 |
|---|---|
9000000000000000000 62 |
1 |
| Sample Input 5 | Sample Output 5 |
|---|---|
5432123456789876543 33 |
4842258985 |
