题目描述

小 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$ 取模之后的答案。

输入格式

共一行，包含两个正整数 $n,k$。

输出格式

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

12 5

18

数据规模与约定

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