3827 - C Bombs

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.

Rezolvare

MOD = 666013

def numar_moduri_detonare(n):

   DP = [0] * (n + 1)
   DP[0] = 1
   for i in range(1, n + 1):
       for j in range(i):
           DP[i] = (DP[i] + DP[j]) % MOD
   return DP[n]

if __name__ == "__main__":

   # Citim datele de intrare
   n = int(input())
   # Calculăm rezultatul și afișăm rezultatul
   rezultat = numar_moduri_detonare(n)
   print(rezultat)