Lucky Days of Penguins

Limits: 2 sec., 256 MiB

Among penguins it is a well known fact that 4 and 7 are lucky digits.

Today \(N\) boxes of ice cream arrived to Madagascar. Each box has a unique integer label between 1 and \(N\), inclusive. The boxes are going to be given away to the penguins in increasing order of their labels. That is the first box given away will be the box with label 1 and the last one will be the box with label \(N\).

The penguins are ordered in a line for the ice cream. While there is an ice cream box left it’s given away to the penguin who is the first one in the line. This penguin counts the total number of lucky digits among all box labels he has. As soon as this number exceeds \(K\) the penguin becomes lucky and leaves the line and the next penguin takes his place.

Your task is to find the number of penguins that are going to be lucky at the end of the described process.

Input

The first line of the input contains the integer \(K\). The second line contains the integer \(N\) without leading zeros.

Output

In the only line of the output print the number of lucky penguins. Since the answer can be quite large output it modulo 1,000,000,007.

Constraints

\(N\) between 1 and \(10^{10000}\).

\(K\) between 1 and 10.

Samples