Hide

Problem C
Powers of 2 (Easy)

/problems/powersof2easy/file/statement/en/img-0001.jpg
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 15\, 000\, 000, 0 \le e \le 25$).

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

Please log in to submit a solution to this problem

Log in