Concurs

Time limit: 1s Memory limit: 64MB Input: concurs.in Output: concurs.out

Î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ă NN 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 NN, 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 666013mod\ 666013.

Restricții și precizări

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

Exemplu

concurs.in

3

concurs.out

13

Explicație

Sunt 1313 clasamente distincte. Pentru 33 concurenți AA, BB și CC, acestea sunt:
(A,B,C)(A, B, C), (A,C,B)(A, C, B), (B,A,C)(B, A, C), (B,C,A)(B, C, A), (C,A,B)(C, A, B), (C,B,A)(C, B, A), (A=B,C)(A=B, C), (A=C,B)(A=C, B), (B=C,A)(B=C, A), (A,B=C)(A, B=C), (B,A=C)(B, A=C), (C,A=B)(C, A=B), (A=B=C)(A=B=C).

În lista de mai sus, am folosit:

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

Log in or sign up to be able to send submissions!