Проверить, делится ли серийный номер некоторого экземпляра игры на 2N

Недавно столкнулся со следующей задачей и не совсем понимаю как её решать. Подскажите пожалуйста в чём вообще идея.

Серийные номера игр компании «1D Software» являются идущими подряд элементами числовой последовательности A. Десятичная запись i-го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого экземпляра игры) и заканчивая i. Например, A2=12, A11=1234567891011.

При этом, если серийный номер некоторого экземпляра игры делится на 2N, то владельцу этого экземпляра доступны дополнительные уровни.

Вам задано количество экземпляров M некоторой игры и число N. Вычислите, сколько экземпляров содержит дополнительные уровни.

В единственной строке входа заданы два целых числа M и N (1 ≤ M ≤ 10^18, 1 ≤ N ≤ 6).

Выведите одно целое число — количество экземпляров игры, содержащих дополнительные уровни

Sample 1
Input
1 1
Output
0

Sample 2
Input
10 1
Output
5

Sample 3
Input
10 2
Output
2

Sample 4
Input
10 3
Output
1

Sample 5
Input
10 4
Output
1

Sample 6
Input
10 5
Output
1

Sample 7
Input
10 6
Output
1

0