Description:


小Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候,所有的整数坐标点上均有一块金子,共N*N块。
一阵风吹过,金子的位置发生了一些变化。细心的小Z发现,初始在(i,j)坐标处的金子会变到(f(i),fIj))坐标处。其中f(x)表示x各位数字的乘积,例如f(99)=81,f(12)=2,f(10)=0。如果金子变化后的坐标不在1..N的范围内,我们认为这块金子已经被移出游戏。同时可以发现,对于变化之后的游戏局面,某些坐标上的金子数量可能不止一块,而另外一些坐标上可能已经没有金子。这次变化之后,游戏将不会再对金子的位置和数量进行改变,玩家可以开始进行采集工作。
小Z很懒,打算只进行K次采集。每次采集可以得到某一个坐标上的所有金子,采集之后,该坐标上的金子数变为0。
现在小Z希望知道,对于变化之后的游戏局面,在采集次数为K的前提下,最多可以采集到多少块金子?
答案可能很大,小Z希望得到对1000000007(10^9+7)取模之后的答案。

Input:


  共一行,包含两介正整数N,K。

Output:


  一个整数,表示最多可以采集到的金子数量。

Sample Input:




Sample Output:


题解:


这个题目第一眼看有一点迷~

可以考虑把两维拆开做。

\(g[i]\) 表示到达 \(i\) 的金子数量。那么 \(g[x]\times g[y]\) 就是二维中的答案。

考虑用数位DP来计算 \(g[i]\) ,设 \(f[i][j][k]\) 表示考虑到第i位,乘积为j,是否大于n的金子数。

然后乱搞一下,因为乘积最多 \(9^{12}\) ,离散化一下可以一维存下。

离散化之前搜出所有的乘积可能情况。

最后可以用类似A*的方法将两维合并,感觉这题令人发抖

代码如下: