Fibonnaci.py

#Q. 4:

#Fibonnaci(Input and Output)

#Chef recently had been studying about Fibonacci numbers and wrote a code to print out the kth term of the Fibonacci series(1, 1, 2, 3, 5, 8, 13.). He was wondering whether he could write a program to generate the kth term for similar series. More specifically : T(n, k) is 1 if n <= k and T(n, k) = T(n-1, k) + T(n-2, k) + T(n-3, k)  + T(n-k, k) if n > k . Given n and k output T(n, k)%(1000000007) as the answer could be very large
#Input
#Two integers, N and K
#Output
#Output description.
#One integer, the nth term of the series mod 1000000007
# 
#Constraints
#1<=N, K<= 2*105
#Example
#Input:
#7 5
#Output:
#9
#Example case 1. The series is as follows {1, 1, 1, 1, 1, 5, 9}


n,k=map(int,input().split())
arr=[1]*k
x=k
for i in range(n-k):
    if i==0:
        arr.append(x)
    else:
        x+=(x-arr[0])
        arr.append(x%1000000007)
        arr.pop(0)
print(arr[-1])