Description

Xiao Z is playing a game called "Prospector." The game world is a 2D coordinate plane. The ranges of the $X$-axis and $Y$-axis coordinates are both $1\ldots N$. Initially, there is one piece of gold at every integer coordinate point, for a total of $N^2$ pieces.

A gust of wind blows by, and the positions of the gold pieces change. The observant Xiao Z notices that the piece initially at $(i,j)$ will move to $(f(i),f(j))$. Here $f(x)$ denotes the product of the digits of $x$, for example $f(99)=81,~f(12)=2,~f(10)=0$.

If the new coordinates of a piece of gold fall outside the range $1\ldots N$, we consider this piece to have been removed from the game. It can also be observed that in the resulting state, some coordinates may have more than one piece of gold, while some coordinates may have none. After this change, the game will no longer alter the positions or quantities of gold; the player can begin collecting.

Xiao Z is lazy and plans to perform only $K$ collections. Each collection can obtain all the gold at a single coordinate; after collecting, the number of gold pieces at that coordinate becomes $0$.

Now Xiao Z wants to know, in the resulting game state, with $K$ collections, what is the maximum number of gold pieces that can be collected? The answer may be large, so Xiao Z wants the answer modulo $10^9+7$.

Input Format

One line containing two positive integers $N, K$.

Output Format

A single integer, the maximum number of gold pieces that can be collected.

12 5

18

Hint

For $100\%$ of the testdata, $N \leq 10^{12}, K \leq \min(N^2, 10^5)$.

Translated by ChatGPT 5