Problem 2782: Expected Nice Numbers

A number is called "nice" if it contains $69$ as a subsequence. In other words, if in that number, immediately after the digit $6$ there is a digit $9$ , then the number is "nice".

For example, the number $369 \ 420$ is "nice", while the number $684 \ 920$ is not "nice".

Task

Given the positive natural numbers $N$ and $K$ , find the expected number of "nice" numbers in a randomly generated sequence containing $N$ numbers with at most $K$ digits, modulo $1 \ 000 \ 000 \ 007$ .

Input data

The program reads from the keyboard the numbers $N$ and $K$ , separated by a newline. The number $K$ is given in base $2$ .

Output data

The program will display on the screen the number $ans$ , representing the required answer in the form $P \cdot {Q}^{-1}$ , modulo $1 \ 000 \ 000 \ 007$ .

Constraints and clarifications

$1 \le N \le {10}^{9}$
$0 \le \log_2(K) < {10}^{6}$
The number $K$ is given in base $2$ .
The use of fastio is recommended.
For tests worth $10$ points, $N \le 10$ , $\log_2(K) \le 3$ .
For other tests worth $20$ points, $N \le 1 \ 000$ , $\log_2(K) \le 20$ .
For other tests worth $20$ points, $N \le 1 \ 000 \ 000$ , $\log_2(K) \le 20$ .
For other tests worth $30$ points, $N \le 1 \ 000 \ 000$ ;
For other tests, no additional restrictions.

Example 1

stdin

1
10

stdout

570000004

Explanation

For simplicity, $N = 1$ , $K = 2$ , so the only allowed nice number is $69$ .
There are $99$ sequences with $0$ "nice" numbers, $1$ sequence with $1$ "nice" number.
Therefore, the answer is $1 \div 100 = 1 \cdot {100}^{-1} = 570 \ 000 \ 004 \pmod{1 \ 000 \ 000 \ 007}$ .

Example 2