aniruddha-and-hackerearth

Aniruddha loves to code on HackerEarth. There are some type of problems which he likes the most.
Problems are tagged with non empty strings containing only 'H' or 'E' or both. But he likes the problems tagged with strings containing no consecutive E's. Given an integer N, find maximum number of problems Aniruddha may like which are tagged with strings of length less than or equal to N.

Input
First line contains single integer, T, the number of test cases.  Each of next T lines contains single integer N.

Output
For each test case output single integer, the answer to the problem i.e maximum number of problems Aniruddha may like which are tagged with strings of length less than or equal to N. Output answer modulo 10^9 + 7 (i.e. 1000000007).

Constraints
1 ≤ T ≤ 10^6
1 ≤ N ≤ 10^6

SAMPLE INPUT
2
2
3

SAMPLE OUTPUT
5
10

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming

Complete search


Solutions:
fib = [2, 3]
sum_fib = [2, 5]
for i in range(1, 10**6 + 1):
	j = (fib[i] + fib[i-1])%1000000007
	fib.append(j)
	sum_fib.append((sum_fib[i] + j)%1000000007)
		
test_cases = int(eval(input()))
for _ in range(test_cases):
	n = int(eval(input()))
	
	print(sum_fib[n-1])	
#return 0
	


arr=[]
sarr=[]
t=0
n=int(input())
if(n>=1 and n<=1000000):
	for i in range(n):
		t=int(input())
		arr.append(t)
		sarr.append(t)
	sarr.sort()
	d ={}
	a =2
	b=3
	ans = a+b
	j=0
	for i in range(1,sarr[n-1]+1):
		if(i>=1 and i<=1000000):
			if(i==1):
				while(j<n and sarr[j]==i):
					d[1]=2
					j=j+1
			if(i==2):
				while(j<n and sarr[j]==i):
					d[2]=5
					j=j+1
			if(i>2):
				temp = (a+b)%1000000007
				ans = (ans+temp)%1000000007
				a=b
				b=temp
				while(j<n and sarr[j]==i):
					d[i]=ans
					j=j+1
		else:
			break
	for i in arr[:]:
		if(i>=1 and i<=1000000):
			print((d[i]))


nums =[]

def process():
	global nums
	nums = [0]*(10**6 + 3)
	nums[1]=2
	nums[2]=3
	
	for i in range(3,10**6 +3):
		nums[i] = (nums[i-1] + nums[i-2])%1000000007
		

def main():
	global nums
	process()
	for _ in range(int(input())):
		print((nums[int(input())+2]-3))
		

main()


nums =[]

def process():
	global nums
	nums.append(0)
	nums.append(2)
	nums.append(3)
	
	for i in range(3,10**6 +3):
		nums.append((nums[i-1] + nums[i-2])%1000000007)
		

def main():
	global nums
	process()
	for _ in range(int(input())):
		print((nums[int(input())+2]-3))
		

main()


nums =[]

def process():
	global nums
	nums = [None]*(10**6 + 3)
	nums[1]=2
	nums[2]=3
	
	for i in range(3,10**6 +3):
		nums[i] = (nums[i-1] + nums[i-2])%1000000007
		

def main():
	global nums
	process()
	for _ in range(int(input())):
		print((nums[int(input())+2]-3))
		

main()


arr=[]
sarr=[]
t=0
n=int(input())
if(n>=1 and n<=1000000):
	for i in range(n):
		t=int(input())
		arr.append(t)
		sarr.append(t)
	sarr.sort()
	d ={}
	a =2
	b=3
	ans = a+b
	j=0
	for i in range(1,sarr[n-1]+1):
		if(i>=1 and i<=1000000):
			if(i==1):
				while(j<n and sarr[j]==i):
					d[1]=2
					j=j+1
			if(i==2):
				while(j<n and sarr[j]==i):
					d[2]=5
					j=j+1
			if(i>2):
				temp = (a+b)%1000000007
				ans = (ans+temp)%1000000007
				a=b
				b=temp
				while(j<n and sarr[j]==i):
					d[i]=ans
					j=j+1
	for i in arr[:]:
		if(i>=1 and i<=1000000):
			print((d[i]))


fib = [2, 3]
sum_fib = [2, 5]
for i in range(1, 10**6 + 1):
	j = (fib[i] + fib[i-1])%1000000007
	fib.append(j)
	sum_fib.append((sum_fib[i] + j)%1000000007)
		
test_cases = int(eval(input()))
for _ in range(test_cases):
	n = int(eval(input()))
	
	print(sum_fib[n-1])	
#return 0
	


fib = [2, 3]
sum_fib = [2, 5]
for i in range(1, 10**6 + 1):
	j = (fib[i] + fib[i-1])%1000000007
	fib.append(j)
	sum_fib.append((sum_fib[i] + j)%1000000007)
		
test_cases = int(input())
for _ in range(test_cases):
	n = int(input())
	
	print(sum_fib[n-1])	
#return 0
	


arr=[]
sarr=[]
t=0
n=int(eval(input()))
if n>=1 and n<=1000000:
	for i in range(n):
		t=int(eval(input()))
		arr.append(t)
		sarr.append(t)
	sarr.sort()
	d ={}
	a =2
	b=3
	ans = a+b
	j=0
	for i in range(1,sarr[n-1]+1):
		if(i>=1 and i<=1000000):
			if(i==1):
				while(j<n and sarr[j]==i):
					d[1]=2
					j=j+1
			if(i==2):
				while(j<n and sarr[j]==i):
					d[2]=5
					j=j+1
			if(i>2):
				temp = (a+b)%1000000007
				ans = (ans+temp)%1000000007
				a=b
				b=temp
				while(j<n and sarr[j]==i):
					d[i]=ans
					j=j+1
		else:
			break
	for i in arr[:]:
		if(i>=1 and i<=1000000):
			print((d[i]))


A = []
A.append(0)
A.append(2)
A.append(3)
B = []
B.append(0)
B.append(2)
B.append(5)
for i in range(1000000):
	A.append(A[-1] + A[-2])
	A[-1] %= 1000000007
	B.append(A[-1] + B[-1])
	B[-1] %= 1000000007
for _ in range(eval(input())):
	n = eval(input())
	print(B[n])