zbc非常喜欢数列，但他实在太弱了无法想象出一个数列该如何构造，于是他就去FD(Frog Department)找srg求助，srg是一名光荣的FTCer(Frog,Time Controller)，并没有很多空闲，就随口给zbc构造了一个神秘的$K$数列，构建方法如下：  
1、创建一个集合$A_K$，集合内包含$K$的所有整数次幂，如当$K=3$时，$A_3$包含$1,3,9,27\dots$，但不会包含$2,4\dots$。  
2、取$A_K$内任意个元素各一个相加，并将他们放进一个新的集合$B_K$。  
3、将$B_K$内的元素从小到大排序，得到的有序数列即是一个$K$数列$S_K$。  
例如当$K=3$时，$S_3=\{1,3,4(3+1),9,10(9+1),12(9+3),13(9+3+1),\dots \}$。  
zbc拿到这个数列后很开心，每天都要盯着这个$K$数列看很久。久而久之这个数列有些数被zbc弄丢了，zbc想复原这个数列，又不好意思再去找srg，他就只能来求助你了。  

zbc想知道$K$数列$S_K$的第$n$项是多少，你可以帮帮他吗？当然这个数有可能会非常大，因此请输出答案对${10}^9+7$取模后的结果。

仅一行包含两个整数$n$和$K$。
1≤n≤1000000000
2≤k≤9

一个整数，表示答案对${10}^9+7$取模后的结果。

想想二进制:在线剪贴板 (nugine.xyz)