It’s well know fact among cats that digits 4 and 7 are lucky digits.

Today, N boxes of ice cream arrived. Each box has a unique integer label on it, ranged between 1 and N, inclusive. The boxes are going to be given away to the cats 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 cats are ordered in line for the ice cream. While there is any ice cream box left, it’s given away to the cat who is the first in line for it. This cat counts the total number of lucky digits among all box labels received by him. As soon as this number exceeds K, the cat becomes lucky and leaves the line, and the next cat occupies his place.

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

Input format

The first line of the input contains the integer K. The second line contains the integer N, without leading zeros.

Output format

In the only line of the output print the number of lucky cats modulo 1,000,000,007.

Constraints

N is between 1 and 10^10000 and K is between 1 and 10, inclusive.