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, $12560$ 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.

-----Examples-----
Sample Input 1:
1000000 1
Sample Output 1:
468559

Sample Input 2:
1000000 5
Sample Output 2:
49401

Sample Input 3:
1000000 16
Sample Output 3:
20

Sample Input 4:
9000000000000000000 62
Sample Output 4:
1

见题面

见题面