╰(￣▽￣)╭

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

一阵风吹过， 金子的位置发生了一些变化。细心的小Z发现， 初始 在(i, j) 坐标 处的金子会变到 (f(i),f(j))坐标 处。其中f(x)表示 x各位数字的乘积 ，例如 ，例如 f(99)=81，f(12)=2，f(10)=0。如果金子变化后的坐标不在 1..N 的范围内，我们认为这块金子已经 被移出游戏。 同时可以发现， 对于变化之后的游戏局面， 某些 坐 标上的金子数量可能 不止一块 ，而另外一些坐标上可能已经没有金子 。这次变化 之后， 游戏将不会再对 金子的位置和数量进行改变，玩家可以开始采集工作。

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

现在小 Z希望知道，对于变化之后的游戏局面，在采集次数为K的前提下， 最多可以采集到少块金子？

答案可能很大，小 Z希望得到1000000007 (10^ 9+7) 取模之后的答案。

(⊙ ▽ ⊙)

横纵坐标可以分开讨论， 为什么？ f()$f()$函数只与其中某一个坐标有关。

然后还要注意到一个性质： 由于f()$f()$只会是0..9$0..9$的数之积，所以质因子只会有2,3,5,7$2,3,5,7$。 这个性质保证了，不同的积不会超过50000$50000$个，并且可以利用数位动态规划预处理出： 这些积分别出现多少次。

现在考虑使用数位动态规划求出这些积分别出现多少次a[]$a[]$。 设fi,j,k,l,o,p$f_{i,j,k,l,o,p}$表示，填了i$i$位数，并且积为2j∗3k∗5l∗7o$2^j*3^k*5^l*7^o$，且当前的i$i$位数是否小于n$n$的前i$i$位（小于等于时p=0$p=0$，否则p=1$p=1$）。 容易转移； 并且也很容易得出每个积分别出现多少次。（满足条件的fi,j,k,l,o,p$f_{i,j,k,l,o,p}$则对a[2j∗3k∗5l∗7o]$a[2^j*3^k*5^l*7^o]$贡献）

知道了a[]$a[]$后，原问题变成找出前k$k$最大的a[i]∗a[j]$a[i]*a[j]$； 做法： 首先对a[]$a[]$从大到小排序，然后先把所有a[i]∗a[1] (i∈[1,len(a[])])$a[i]*a[1]/ (i∈[1,len(a[])])$放入线段树的对应位置； 显然对线段树进行k$k$次最值查询； 每次查询后得到最值的位置，把这一位第二项的a[]$a[]$往后取一位。

(￣～￣)

(⊙v⊙)

1.对于f(x)$f(x)$这种一元函数，可以单独考虑和讨论。 2.对积的质因子敏感，例如本题，只有2,3,5,7$2,3,5,7$这四个质因子。