Iacob Tudor (IacobTudor) Cerința
Le Quack vrea să bombardeze un oraș având N bombe numerotate de la 1...N. Dacă el detonează bombă cu valorea i atunci va putea să detoneze doar bombe încă nedetonate cu valori mai mici decât i. În cazul în care nu mai există astfel de bombe , poate detona orice bombă nedetonata. Le Quack va da numărul N și vrea să îi spuneți în câte moduri poate detona toate cele N bombe după regulă descrisă anterior.
Date de intrare
Inputul conține un număr natural n , reprezentând numărul de bombe pe care le are Le Quack.
Date de ieșire
Outputul conține răspunsul modulo 666013.
Restricții și precizări
N ≤ 2000.- Pentru teste în valoare de 10p,
N ≤ 9. - Pentru restul testelor în valoare de 90p,
N ≤ 2000.
Exemplu:
bombs.in
2
bombs.out
2
bombs.in
3
bombs.out
5
Explicație
În primul exemplu, configurațiile posibile sunt: [1 , 2] și [2 , 1].
În al doilea exemplu, configurațiile posibile sunt: [1 , 2 , 3] , [3 , 2 , 1] , [2 , 1 , 3] , [3 , 1 , 2] , [1 , 3 , 2]. Configurația [2 , 3 , 1] nu este bună, deoarece am luat bombă 3 înainte să termin toate bombele cu indici mai mici decât 2, ceea ce contrazice regula lui Le Quack.