Hackerearth string problem : Solution in Python

PROBLEM STATEMENT

Points: 30

Two letter strings are the strings consisting of only two letters "X" and "Y". A string is "super two letter string" if

a) It does not have leading "X" letters.
b) It does not contain P consecutive "X" letters.

Your task is to find total number of Super two letter strings of length N.

Input :

The first line contains the number of test cases T . Each test case consists of two space separated integers - N and P .

Output :

For each test case output total number of Super two letter strings of length N modulo 1000000007(10^9+7).

Constraints :

1 <= T <= 100

1 <= N <= 10^4

1 <= P <= 10

SAMPLE INPUT

2
2 1
4 2

SAMPLE OUTPUT

1
5

Explanation

For first sample : Only possible string is : YY For second sample : Possible strings are : YXYX , YXYY, YYYX, YYXY, YYYY

Solution  in   Python

import math
import array
ar = array.array('i',[]);
i = 1
c=0
T = input()
while i <=int(T):
    N1 = input()
    n2 = N1
    n = int(n2.split()[0])-1
    P = int(n2.split()[1])
    a=[0 for i in range(n)]
    b=[0 for i in range(n)]
    a[0] = b[0] = 1
    for i in range(1,n):
        a[i] = a[i-1] + b[i-1]
        b[i] = a[i-1]
        c+=a[n-1] + b[n-1]
    ar.append(c)
    i+=1
for j in ar :
    print(j)