cuvinte

Se consideră un alfabet $A$ format din literele X, Y și Z. Rică a început să se deprintă cu tehnici de numărare a cuvintelor. Astfel, acum dorește să numere cuvintele formate cu literele alfabetului $A$ de lungime $N$, astfel încât să nu existe două litere egale pe poziții vecine.

Cerință

Cunoscând $N$ se cere să se determine:

1. Cel mai mare cuvânt de lungime $N$ în ordine alfabetică din alfabetul $A$, care să nu conțină două litere egale pe poziții vecine.
2. Numărul de cuvinte formate cu literele alfabetului $A$ de lungime $N$, astfel încât să nu existe două litere egale pe poziții vecine.

Date de intrare

Pe prima linie a fișierului de intrare cuvinte.in se găsește $C$, numărul corespunzător cerinței ce se va rezolva ($1$ sau $2$). Pe linia a doua se va afla $N$.

Date de ieșire

Pe prima linie a fișierului de ieșire cuvinte.out se va găsi răspunsul la cerința corespunzătoare fișierului de intrare.

Restricții și precizări

• $1 \leq N \leq \ 30 \ 000$;
• Două litere sunt vecine într-un cuvânt, dacă se găsesc pe poziții consecutive;
• Pentru rezolvarea corectă a cerinței $1$ se vor acorda $20$ de puncte.
• Pentru rezolvarea corectă a cerinței $2$ se vor acorda $80$ de puncte.

Exemplul 1

cuvinte.in

1
3

cuvinte.out

ZYZ

Explicație

Cel mai mare cuvânt în ordine alfabetică cu litere din alfabetul $A$ este ZYZ, ce respectă restricția din cerinta $C = 1$!

Exemplul 2

cuvinte.in

2
2

cuvinte.out

6

Explicație

Cuvintele ce se pot forma cu $N = 2$, ce respectă restricția din cerința $C = 2$ sunt XY, XZ, YX, YZ, ZX, ZY.