Flavia este interesată de şirurile de $N$ *$a$*-uri şi *$b$*-uri unde nu există trei caractere adiacente egale. De exemplu, *$abaaba$* se incadrează în această definiţie, dar *$abaaa$* nu.  Şirurile care satisfac această definiţiele le vom numi _interesante_.

Flaviei îi pasă de aceste şiruri din punctul de vedere a ordonării lexicografice. Pentru două şiruri $A$ şi $B$ de lungime $N$ spunem ca $A$ este mai mic ca $B$ în ordinea lexicografică dacă şi numai dacă, pentru ceva indice $i$ unde $1 &le; i &le; N$ , avem $A[$1$] = B[$1$]$, ..., $A[i−1] = B[i−1]$ şi $A[i] < B[i]$. De exemplu, $*aba*$ este mai mare ca $*aab*$ în ordine lexicografică, dar mai mic ca $*baa*$ în ordine lexicografică.

Flaviei îi pasă de aceste şiruri din punctul de vedere a ordonării lexicografice.  Pentru două şiruri $A$ şi $B$ de lungime $N$ spunem ca $A$ este mai mic ca $B$ în ordinea lexicografică dacă şi numai dacă, pentru ceva indice $i$ unde $1 &le; i &le; N$ , avem $A[$1$] = B[$1$]$ , ..., $A[i−1] = B[i−1]$ şi $A[i] < B[i]$. De exemplu, $*aba*$ este mai mare ca $*aab*$ în ordine lexicografică, dar mai mic ca $*baa*$ în ordine lexicografică.

Flavia acum vrea să rezolve două cerinţe:
# Dându-se un şir $S$ interesant de lungime $N$, să se găsească al câtelea este el, în ordine lexicografică, printre toate şirurile interesante de lungime $N$, modulo $10^9^+7$