#P3303. [SDOI2013] 淘金

[SDOI2013] 淘金

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

12 5
18

提示

对于 100%100\% 的数据,N1012,Kmin(N2,105)N \leq 10^{12}, K \leq \min(N^2, 10^5)