Fişierul intrare/ieşire:	cntlex.in, cntlex.out	Sursă	Science On 2021, clasa 7-8
Autor	Tamio-Vesa Nakajima	Adăugată de	Voicu Mihai Valeriu •cadmium_
Timp execuţie pe test	0.3 sec	Limită de memorie	268435 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 ≤ i ≤ N , avem A[1] = B1, ..., 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:

1. 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⁹+7
2. 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?

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

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⁹+7.
Dacă P=2, fişierul de ieşire va conţine al K-lea şir interesant de lungime N în ordine lexicografică.

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

Exemplu

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

Cum se trimit solutii?