Avem un coridor lung de lățime k și lungime n. Avem sarcina de a-l acoperi cu bucăți de gresii de dimensiuni 1 x k, 2 x k și 3 x k. De exemplu, pentru k = 3 și n = 4, avem 13 moduri distincte de pavare:

Cerința

Calculați în câte moduri distincte se poate acoperi coridorul cu cele 3 tipuri de gresii. Pentru că rezultatul este un număr mare, se cere restul împărțirii la 1.000.000.007.

Date de intrare

Fișierul standard de intrare conține pe prima linie două numere naturale k și n separate prin spațiu.

Date de ieșire

Fișierul standard de iesire va conține pe prima linie un singur număr natural, ce reprezintă numărul pavărilor distincte modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ k ≤ 25
• 3 ≤ n ≤ 2.000.000.000
• k ≤ n

Exemplul 1:

Intrare

3 4

Ieșire

13

Exemplul 2:

Intrare

24 12345678

Ieșire

928757352