slang

SLang este o versiune a aplicației Scratch care pune la dispoziție șapte instrucțiuni de tip $I1$, $I2$, $I3$, $I4$, $I5$, $I6$, $I7$ prezentate în imaginea alăturată.
Un program corect este o succesiune de instrucţiuni care respectă următoarele reguli:

1. Începe cu o instrucțiune de tip $I1$ şi se termină cu o instrucțiune de tip $I7$.
2. Între instrucţiunea de tip $I1$ şi instrucţiunea de tip $I7$ vor exista una, două sau mai multe instrucţiuni de tipurile $I2$, $I3$, $I4$, $I5$ sau $I6$, fără a utiliza două instrucţiuni de acelaşi tip; fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.
3. Corpul unei instrucțiuni de tip $I4$ poate conține una sau două instrucțiuni de mișcare (adică de tip $I2$ sau $I3$) și nu poate conține instrucțiuni de alt tip.

De exemplu:

4. Fiecare dintre cele două ramuri ale unei instrucțiuni de tip $I5$ (ramura daca şi ramura daca nu) poate conține una sau două instrucțiuni de tip $I2$ sau $I3$ și nu poate conține instrucțiuni de alt tip.
5. Corpul unei instrucțiuni de tip I6 poate conține una, două sau mai multe instrucţiuni de tipurile $I2$, $I3$, $I4$, $I5$ sau $I6$, fără a utiliza două instrucţiuni de acelaşi tip; similar, fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.

Nivelul de imbricare al unui program corect va fi egal cu numărul de instrucţiuni de tip $I6$ existente în program.

Exemplu de program corect cu trei instrucțiuni de tip $I6$ (program cu nivelul de imbricare $3$).	Exemplu de program incorect deoarece o instrucțiune de tip $I5$ nu poate conține o instrucțiune de tip $I6$.

Cerinţă

Dat fiind numărul natural $K$, reprezentând nivelul de imbricare, scrieţi un program care să rezolve următoarele cerinţe:

1. determină numărul de programe corecte distincte cu nivelul de imbricare $K$;
2. determină numărul minim de instrucțiuni și respectiv numărul maxim de instrucțiuni ce pot exista într-un program corect cu nivel de imbricare $K$.

Date de intrare

Fișierul de intrare slang.in conține pe prima linie un număr natural $c$ reprezentând cerinţa care trebuie să fie rezolvată ($1$ sau $2$).Pe cea de a doua linie se află numărul natural $K$, reprezentând nivelul de imbricare.

Date de ieșire

Dacă $c=1$, atunci se va rezolva numai cerința $1$, caz în care pe prima linie a fișierului slang.out va fi scris un număr natural reprezentând ultimele șase cifre ale numărului de programe corecte distincte care au nivelul de imbricare K.
Dacă $c=2$, atunci se va rezolva numai cerința $2$. În acest caz, fișierul de ieșire slang.out va conține pe prima linie două numere naturale separate printr-un spațiu, reprezentând numărul minim de instrucțiuni, respectiv numărul maxim de instrucțiuni ale unui program corect cu nivel de imbricare $K$.

Restricții și precizări

• $0 \leq K \leq 1 \ 000$
• Două programe sunt distincte dacă în succesiunile de instrucţiuni corespunzătoare există cel puţin o poziţie pe care se află instrucţiuni de tipuri diferite.
• Se garantează că, pentru datele de test, prima dintre cele $6$ cifre cerute, este nenulă.
• Pentru rezolvarea corectă a fiecărei cerinţe se acordă $50$ de puncte.

Exemplul 1

slang.in

1
0

slang.out

8674

Explicație

Cerinţa este $1$.
Există $8 \ 674$ de programe corecte distincte cu nivelul de imbricare $0$.

Exemplul 2

slang.in

2 0

slang.out

3 12

Explicație

Cerinţa este $2$.
Numărul minim de instrucţiuni dintr-un program corect cu nivelul de imbricare $0$ este $3$. Un exemplu de astfel de program este:

Numărul maxim de instrucţiuni dintr-un program corect cu nivelul de imbricare $0$ este $12$. Un exemplu de astfel de program este: