407950: GYM102947 K Call of the Wild

Buck has settled into life as a pack wolf after answering the call of the wild. However, he is often required to defend his title as leader of the pack due to his domesticated past. All pack wolves are masters of mathematics, so it is only natural that they spar by asking for solutions to computational problems. The challenger asks Buck to count the number of whole numbers at most $$$N$$$ that contain $$$2^x$$$ as a substring. Even with the vast knowledge of combinatorial techniques, the sheer size of $$$N$$$ makes it difficult for our favorite St. Bernard–Scotch Collie mix to calculate the answer mentally. Can you help Buck live up to his reputation as "Ghost Dog" of the Northland by finding this result?

The input consists of one line of two space separated integers, $$$N$$$ ($$$0 \leq N \leq 9 \cdot 10^{18}$$$) and $$$x$$$ ($$$0 \leq x \leq 62$$$), which are described above.

A single integer representing the number of distinct whole numbers at most $$$N$$$ whose decimal form contains the digits of $$$2^x$$$ as a substring.

1000000 1

468559

1000000 5

49401