numarare

Rică este elev in clasa a XII-a si doreste sa devina student la specializarea informatică din Politehnica București - Centrul Universitar Pitești. Pentru acest lucru se pregătește să dea bacalaureatul la informatică. Recapitulând principalele noțiuni din teoria grafurilor a dat peste două probleme de numărare. Pentru $N$ dat, la prima problemă trebuie să determine numărul de grafuri neorientate cu $N$ noduri în care nodul $1$ este terminal, iar la a doua problemă trebuie să determine numărul de arbori cu nodul $1$ nod terminal, iar gradul nodului $2$ este cel puțin $2$. Nodurile grafurilor și arborilor sunt etichetate cu $1, 2, \dots, N$.

Cerință

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

1. numărul de grafuri neorientate cu $N$ noduri în care nodul $1$ este terminal, modulo $7919$
2. numărul de arbori cu nodul $1$ nod terminal, iar gradul nodului $2$ este cel puțin $2$, modulo $7919$

Date de intrare

Pe prima linie a fișierului de intrare numarare.in se găsește $C$ numărul cerinței ($1$ sau $2$), iar pe linia a doua $N$.

Date de ieșire

Pe prima linie a fișierului de ieșire numarare.out se va găsi un singur număr natural, ce reprezintă numărul corespunzător cerinței ce trebuie rezolvată.

Restricții și precizări

• $1 \leq N \leq 15 \ 000$;
• $A$ modulo $k$ este $A \ \% \ k$;
• 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

numarare.in

1
3

numarare.out

4

Explicație

În figura de mai jos sunt desenate cele $4$ grafuri.

Exemplul 2

numarare.in

2
4

numarare.out

5

Explicație

În figura de mai jos sunt desenați cei $5$ arbori.