Gold Collector: The Prospectors' Game

In the game Gold Collector: The Prospectors' Game, the world is represented by a 2D grid of coordinates, where both the $X$ and $Y$ axes range from $1$ to $N$. Initially, there is exactly one gold coin at every integer coordinate, for a total of $N^2$ coins.

A sudden gust of wind moves the coins. Every coin originally at coordinate $(i,j)$ is shifted to coordinate \( (f(i),f(j)) \), where \( f(x) \) is defined as the product of the digits of \( x \). For example, \( f(99)=9\times 9=81 \), \( f(12)=1\times 2=2 \), and \( f(10)=1\times 0=0 \). If after the transformation a coin ends up at a coordinate not in the range \( [1,N] \) (i.e. if either coordinate is less than 1 or greater than N), that coin is removed from the game.

After the shift, some coordinates may accumulate more than one coin while others may have none. The game then enters the collection phase. The player, being a bit lazy, is allowed to perform exactly \( K \) collection moves. In each move, the player may select any coordinate and collect all coins present there (after which the coin count at that cell becomes 0).

Your task is to determine the maximum number of coins that can be collected in \( K \) moves, modulo \( 10^9+7 \).

Hint: Notice that every coin originally at coordinate \( (i,j) \) ends up at \( \bigl(f(i), f(j)\bigr) \). Let \( A[x] \) be the number of integers \( i \) (with \( 1 \le i \le N \)) such that \( f(i)=x \) and also \( 1\le x \le N \) (coins with coordinate 0 or >N are removed). Then, the number of coins at coordinate \( (x,y) \) in the final configuration is \( A[x]\times A[y] \). The goal is to choose up to \( K \) distinct coordinates (cells) with the highest coin counts to maximize the total collected coins.

inputFormat

The input consists of a single line containing two integers \( N \) and \( K \) (separated by a space), where \( 1 \le N \le \text{some upper limit} \) and \( 1 \le K \le N^2 \).

outputFormat

Output a single integer, the maximum number of coins that can be collected using exactly \( K \) moves, modulo \( 10^9+7 \).

sample

5 1

25