Problem10650--洛谷P3303 - [SDOI2013] 淘金

10650: 洛谷P3303 - [SDOI2013] 淘金

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

小 Z 在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。$X$ 轴、$Y$ 轴坐标范围均为$1\ldots N$。初始的时候,所有的整数坐标点上均有一块金子,共 $N^2$ 块。

一阵风吹过,金子的位置发生了一些变化。细心的小 Z 发现,初始在 $(i,j)$ 坐标处的金子会变到 $(f(i),f(j))$ 坐标处。其中 $f(x)$ 表示 $x$ 各位数字的乘积,例如 $f(99)=81,~f(12)=2,~f(10)=0$。

如果金子变化后的坐标不在 $1\ldots N$ 的范围内,我们认为这块金子已经被移出游戏。同时可以发现,对于变化之后的游戏局面,某些坐标上的金子数量可能不止一块,而另外一些坐标上可能已经没有金子。这次变化之后,游戏将不会再对金子的位置和数量进行改变,玩家可以开始进行采集工作。

小 Z 很懒,打算只进行 $K$ 次采集。每次采集可以得到某一个坐标上的所有金子,采集之后,该坐标上的金子数变为 $0$。

现在小 Z 希望知道,对于变化之后的游戏局面,在采集次数为 $K$ 的前提下,最多可以采集到多少块金子? 答案可能很大,小 Z 希望得到对 $10^9+7$ 取模之后的答案。

Input

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

Output

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

Constraints

对于 $100\%$ 的数据,$N \leq 10^{12}, K \leq \min(N^2, 10^5)$。

Sample 1 Input

12 5

Sample 1 Output

18

HINT

洛谷P3303

Source/Category

数位DP