== include(page="template/taskheader" task_id="cntlex") ==

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_.

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$

# Dându-se un număr $N$ şi un număr $K$ să se găseasca al $K$-lea şir interesant de lungime $N$ în ordine lexicografică. O puteţi ajuta?

# Dându-se un număr $N$ şi un număr $K$ să se găseasca al $K$-lea şir interesant de lungime $N$ în ordine lexicografică.
 
O puteţi ajuta?

h2. Date de intrare

Primul rând al fişierului de intrare conţine numărul $P$,  indicele cerinţei din test.  Pe al doilea rând al inputului se va găsi numărul $N$.

Primul rând al fişierului de intrare conţine numărul $P$, indicele cerinţei din test. Pe al doilea rând al inputului se va găsi numărul $N$.

Dacă $P=1$, pe al treilea rând se va găsi şirul $S$ interesant.
Dacă $P=2$, pe al treilea rând se va găsi numărul $K$

h2. Restricţii

* Pentru teste in valoare de $20$ de puncte, $P=1$ şi $N ≤ 20$
* Pentru teste in valoare de $30$ de puncte, $P=1$ şi $N ≤ 1 000 000$
* Pentru teste in valoare de $20$ de puncte, $P=2$. $N ≤ 100$ şi $K ≤ 1 000 000$
* Pentru teste in valoare de $30$ de puncte, $P=2$. $N ≤ 1 000 000$ şi $K ≤ 1 000 000 000$

* Pentru teste în valoare de $20$ de puncte, $P=1$ şi $N ≤ 20$
* Pentru alte teste în valoare de $30$ de puncte, $P=1$ şi $N ≤ 1 000 000$
* Pentru alte teste în valoare de $20$ de puncte, $P=2$, $N ≤ 100$ şi $K ≤ 1 000 000$
* Pentru alte teste în valoare de $30$ de puncte, $P=2$, $N ≤ 1 000 000$ şi $K ≤ 1 000 000 000$

h2. Exemplu