Un număr se numește “nice” dacă conține $69$ ca subsecvență. În alte cuvinte, dacă în numarul respectiv, imediat după o cifra $6$ se află o cifră $9$, numărul respectiv este “nice”.

De exemplu, numărul $369 \ 420$ este “nice”, pe când numărul $684 \ 920$ nu este “nice”.

Cerința

Se dau numerele naturale nenule $N$ și $K$. Să se afle numărul așteptat de numere “nice” într-un șir generat aleatoriu care conține $N$ numere de cel mult $K$ cifre, modulo $1 \ 000 \ 000 \ 007$.

Date de intrare

Programul citește de la tastatură numerele $N$ și $K$, separate prin newline. Numărul $K$ este dat în baza $2$.

Date de ieșire

Programul va afișa pe ecran numărul $ans$, reprezentând răspunsul cerut scris sub forma de $P \cdot {Q}^{-1}$, modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \le N \le {10}^{6}$
• $0 \le log_2(K) < {10}^{6}$
• Numărul $K$ este dat în baza $2$.
• Se recomandă folosirea fastio

Punctare

• Pentru teste în valoare de $10$ puncte, $N \le 10, \ log_2(K) \le 3$;
• Pentru alte teste în valoare de $20$ puncte, $N \le 1 \ 000, \ log_2(K) \le 20$;
• Pentru alte teste în valoare de $20$ puncte, $N \le 1 \ 000 \ 000, \ log_2(K) \le 20$;
• Pentru celelalte teste, nicio restricție suplimentară.

Exemplu 1

Intrare

1
10

Ieșire

570000004

Explicație

Pentru simplitate, $N = 1, \ K = 2$, așa că singurul număr nice admis este $69$.

Există $99$ de șiruri cu $0$ numere “nice”, $1$ șir cu $1$ număr “nice”.

Așadar, răspunsul este $1 \div 100 = 1 \cdot {100}^{-1} = 570 \ 000 \ 004$ modulo $1 \ 000 \ 000 \ 007$.

Exemplu 2

Intrare

5
10

Ieșire

850000006