4032 - Zar 1

Cerința

În câte moduri se poate obține suma n aruncând cu zarul (În câte moduri poți să îl scrii pe n ca sumă de valori mai mici sau egale cu 6).

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran răspunsul la întrebarea din enunț.

Restricții și precizări

1≤n≤1018 Rezultatul se va afișa modulo 109+7 . ==Exemplu==: Intrare

8 Ieșire

125

Explicație

Câteva dintre posibilități ar fi 1 + 1 + 6, 2 + 5 + 1, 1 + 6 + 1 …

Rezolvare

MOD = 10**9 + 7

def numar_moduri_suma(n):

   # Initializăm lista cu 0-uri
   dp = [0] * (n + 1)
   # Există o singură modalitate de a obține suma 0, adică nu aruncăm zarul
   dp[0] = 1
   # Calculăm numărul de moduri pentru fiecare sumă posibilă
   for i in range(1, n + 1):
       for j in range(1, 7):
           if i - j >= 0:
               dp[i] = (dp[i] + dp[i - j]) % MOD
   return dp[n]

if __name__ == "__main__":

   n = int(input("Introduceți suma n: "))
   rezultat = numar_moduri_suma(n)
   print(rezultat)