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