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 $369420$ este “nice”, pe când numărul $684920$ 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 $1000000007$.

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 $1000000007$.

Restricții și precizări

• $1\le N\le {10}^6$
• $0\le lo{g}_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,lo{g}_2(K)\le 3$;
• Pentru alte teste în valoare de $20$ puncte, $N\le 1000,lo{g}_2(K)\le 20$;
• Pentru alte teste în valoare de $20$ puncte, $N\le 1000000,lo{g}_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÷100=1\cdot {100}^{-1}=570000004$ modulo $1000000007$.

Exemplu 2

Intrare

5
10

Ieșire

850000006