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

`stdin`

```
5
10
```

`stdout`

```
850000006
```