Simulation - Info-Oltenia 2024 X | Concurs

În fiecare an, restaurantul Vila Elena organizează un concurs de mâncat grătare la 7 lei destinat celor mai fideli clienți. În acest concurs, scorul fiecărui participant este determinat de numărul de grătare mâncate într-o oră.

Din cauza acestei metode de ordonare, se întâmplă foarte des ca mai mulți participanți să obțină același scor, adică să consume același număr de grătare. În acest caz, cei cu același scor vor împărți aceeași poziție în clasament.

Cerință

Știind că în ediția de anul acesta a concursului de mâncat participă $N$ clienți ai restaurantului, care este numărul de clasamente distincte care pot fi obținute la finalul concursului?

Date de intrare

Pe prima linie a fișierului de intrare concurs.in se găsește un număr natural $N$, reprezentând numărul de clienți care participă la concurs.

Date de ieșire

Pe prima linie a fișierului de ieșire concurs.out se va găsi un singur număr natural, numărul de clasamente distincte $mod\ 666013$.

Restricții și precizări

• $1 \leq N \leq 5 \ 000$;
• Pentru $30\%$ din teste, $N \lt 10$.

Exemplu

concurs.in

3

concurs.out

13

Explicație

Sunt $13$ clasamente distincte. Pentru $3$ concurenți $A$, $B$ și $C$, acestea sunt:
$(A, B, C)$, $(A, C, B)$, $(B, A, C)$, $(B, C, A)$, $(C, A, B)$, $(C, B, A)$, $(A=B, C)$, $(A=C, B)$, $(B=C, A)$, $(A, B=C)$, $(B, A=C)$, $(C, A=B)$, $(A=B=C)$.

În lista de mai sus, am folosit:

• $(A, B, C)$ pentru a desemna clasamentul în care $A$ este pe prima poziție, $B$ este pe a doua poziție iar $C$ este pe a treia.
• $(A=B, C)$ pentru clasamentul în care $A$ și $B$ împart locul unul, iar $C$ este pe locul doi.
• $(A=B=C)$ pentru clasamentul în care $A$, $B$ și $C$ împart toți primul loc.