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

Poveste şi cerinţă...

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?

h2. Date de intrare

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

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. Date de ieşire

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

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

h2. Restricţii

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

* 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
table(example). |_. cntlex.in |_. cntlex.out |

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

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

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") ==