题目描述

给你一个整数$\red{k}$和$\red{b，}$计算在区间$\red{[0,2^b-1]}$内的每一个能够被$\red{k}$整除的数中的二进制的$\red{1}$的个数。

最后将答案对$\red{1000000009}$取模

输入格式

输入两个数$\red{k}$和$\red{b}$。其中$\red{1<=k<=1000,1<=b<=128}$。

输出格式

一行输出答案。

样例

输入样例

1 4

输出样例

32

提示

数据范围：

对于$\red{10\%}$的数据，$\red{1 ≤}$ $\red{b ≤}$ $\red{16}$

对于$\red{20\%}$的数据，满足$\red{1 ≤}$ $\red{b ≤}$ $\red{32}$

对于$\red{30\%}$的数据，满足$\red{1 ≤}$ $\red{b ≤}$ $\red{64}$

对于$\red{100\%}$的数据，满足$\red{1 ≤}$ $\red{b ≤}$ $\red{128}$