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

Poveste şi cerinţă...

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

Fişierul de intrare $cntlex.in$ ...

h2. Date de ieşire

Dacă $P=1$, fişierul de ieşire va conţine un număr întreg, al câtelea şir interesant de lungime $N$ este $S$,modulo $10^9^+7$.
Dacă $P=2$, fişierul de ieşire va conţine al $K$-lea şir interesant de lungime $N$ în ordine lexicografică.

În fişierul de ieşire $cntlex.out$ ...

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$
 

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. cntlex.in |_. cntlex.out |

| 1
  3
  aba
| 2 |
| 2
  3
  5
| bab
| bab

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

Şirurile interesante de lungime 3, în ordine lexicografică, sunt *$aab, aba, abb, baa, bab, bba$*. Astfel *$aba$* este al $2$-lea în ordine lexicografică, şi al $5$-lea este *$bab$*

...

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