concursuri

Studenții anului 1 de la Informatică din Politehnica București - Centrul Universitar Pitești în număr de $N$, codificați prin $1, 2, \dots, N$, trebuie să participe la două concursuri în perioade diferite de timp. La primul concurs trebuie să trimită o echipă, iar la cel de-al doilea trei echipe. La primul concurs echipa poate avea cel puțin un student și cel mult $N$ studenți. La al doilea concurs echipele au câte un nume PBCUP1, PBCUP2, PBCUP3 și conțin cel puțiun un student fiecare. Nu are importanță ordinea în echipă și un student poate participa la al doilea concurs numai într-o echipă din cele trei.

Cerință

Cunoscând $N$ numărul de studenți se cere:

1. În câte moduri se poate alege echipa pentru primul concurs.
2. În câte moduri se pot alege echipele PBCUP1, PBCUP2, PBCUP3 pentru al doilea concurs. Acest număr se cere modulo $7919$.

Date de intrare

Pe prima linie a fișierului de intrare concursuri.in se găsește $C$, numărul cerinței ce trebuie rezolvată, iar pe linia a doua numărul de studenți $N$.

Date de ieșire

Pe prima linie a fișierului de ieșire concursuri.out se va găsi un singur număr natural, ce reprezintă valoarea corespunzătoare cerinței $C$ din fișierul de intrare.

Restricții și precizări

• $3 \leq N \leq 15 \ 000$;
• $A$ modulo $k$ reprezintă restul împărțirii lui $A$ la $k$, adică $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

concursuri.in

1
3

concursuri.out

7

Explicație

In acest caz se rezolvă cerința $C = 1$. Echipele pentru primul concurs pot fi $[1]$, $[2]$, $[3]$, $[1 2]$, $[1 3]$, $[2 3]$ și $[1 2 3]$.

Exemplul 2

concursuri.in

2
3

concursuri.out

6

Explicație

In acest caz se rezolvă cerința $C =2$. Echipele PBCUP1, PBCUP2, PBCUP3 pentru primul concurs pot fi: $([1],[2],[3])$, $([1],[3],[2])$, $([2],[1],[3])$, $([2],[3],[1])$, $([3],[1],[2])$, $([3],[2],[1])$. Deci sunt $6$ variante pentru a participa la al doilea concurs.