binary-strings

Golu hates odd numbers. When he learns about binary strings he wants to find out how many binary strings of given length N exist without an odd number of consecutive 1's.

For example: For N=4 1001,1010,1110,0001 are strings which contain odd number of 1's where 1100,1111 are not. Leading zeros are allowed.

This task is very difficult for Golu he asks you for your help.
Now your task is to find how many strings of given length exist without any consecutive 1's.

INPUT First line contains number of test cases T.Each test case contains length of binary string N.
OUTPUT Print number of strings without consecutive 1's. Output become large so take module with 1000000007.
Constraints
1 ≤ T ≤ 100

1 ≤ N ≤ 1000000

SAMPLE INPUT
1
2

SAMPLE OUTPUT
2

Explanation

For N=2 Binary strings are 00 , 01 , 10 , 11 and number of strings without  odd number of consecutive 1's are 2.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
a=[1,1]
for x in range(2,1000007):
	a.append((a[x-1]+a[x-2])%1000000007)
for x in range(eval(input())):
	n=eval(input())
	print(a[n])


MOD=1000000007
a=[1,2]
for i in range(2,100000):
	a.append((a[i-1]+a[i-2])%MOD)
for _ in range(eval(input())):
	x=eval(input())
	print(a[x-1])
	


a = [0]*(1000005)
b = [0]*(1000005)
def cstr():
	a[0] = 1
	for i in range(1, 1000000+1):
		a[i] = (a[i-1] + b[i-1]) % 1000000007
		b[i] = a[i-1] % 1000000007
#	return (a[n-1] + b[n-1]) % 1000000007

t = eval(input())
cstr()
while t>0:
	t-=1
	n = eval(input())
#	cnt = cstr(n)
	print((a[n-1] + b[n-1]) % 1000000007)


a=[]
a.append(0)
a.append(1)
a.append(2)
for i in range(3,1000001):
	a.append((a[i-1]%1000000007+a[i-2]%1000000007)%1000000007)


t=int(eval(input()))

for i in range(0,t):
	n=int(eval(input()))
	print((a[n]))
	


MOD=1000000007
a=[1,2]
for i in range(2,100000):
	a.append((a[i-1]+a[i-2])%MOD)
for _ in range(eval(input())):
	x=eval(input())
	print(a[x-1])