给出 kkk 和 bbb，计算 [0,2b−1][0, 2^b-1][0,2b−1] 中所有 kkk 的倍数都转成二进制后共出现几个 111，答案对 109+910^9+9109+9 取模。
输入
一行两个整数，k,b (1≤k≤1000,1≤b≤128)k,b \ (1 \leq k \leq 1000, 1 \leq b \leq 128)k,b (1≤k≤1000,1≤b≤128)。
输出
一个整数，表示答案。
样例
1 4
32
10 5
8
3 28
252698795
提示
样例二中，[0,31][0,31][0,31] 中 101010 的倍数有 0,10,20,300,10,20,300,10,20,30，他们的二进制形式为 0,1010,10100,111100,1010,10100,111100,1010,10100,11110，一共 888 个 111。