zeroshark

A binary string of length N is a string of N characters, where each character is either 0 or 1. 

Wet Shark makes a list binStrings, consisting of all 2^N N-digit binary strings. For each string X in binStrings, Wet Shark runs a function ZeroShark(X), defined as follows (psuedocode):

bool ZeroShark(x):
//note the zero indexing
n = length(x)
counter = 0
FOR i = 1 to n-1
    IF x[i] == '0' and x[i - 1] == '0'
        INCREMENT counter
        END IF
ENDFOR
return (counter == 1)

Wet Shark stores an element X in a new list, binTrues  if ZeroShark(X) returns True for that X . In otherwords, binTrues consists of all the elements X in binStrings such that ZeroShark(X) returns True.

Given T testcases, where each testcase consists of integer N, calculate the length of binTrues for each N. Because the lists can get large, output your answer modulo 10^9+7=1000000007

INPUT

The first line of the input contains a single integer T, the number of such N.

The next T lines of the input contain a single integer N, as described in the problem.

OUTPUT

Output T separate lines, each containing the number of elements in the resulting list binTrues for each N in the input. The lists may be large, so output the answer modulo 10^9+7=1000000007

CONSTRAINTS

1 ≤ T ≤ 10

1 ≤ N ≤ 10^5

SAMPLE INPUT
2
2
3

SAMPLE OUTPUT
1
2

Explanation

When N=2, the list binStrings is equal to ['00', '01', '10', '11'].

Calling ZeroShark on each element in binStrings, the function only returns true when X is equal to 00. When X = 01, 10, 11, the counter in ZeroShark is equal to 0. 

Therefore, binTrues is equal to ['00'], and has a length of 1.

When N=3, the list binStrings is equal to ['000', '001', '010', '100', '011', '101', '110', '111'].

Calling ZeroShark on each element in binStrings, the function only returns true when X is equal to 001 or 100. 

Therefore, binTrues is equal to ['001', '100'], and has a length of 2.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
lista = []
for i in range(int(eval(input()))):
	n = int(eval(input()))
	dp = [0, 0, 1] + [0] * (n-2)
	fib = [0, 1, 1] + [0] * (n-3)
	for i in range(3, n):
		fib[i] = (fib[i-1] + fib[i-2]) % (10**9+7)
	for i in range(3, n+1):
		dp[i] = (dp[i-1] + dp[i-2] + fib[i-1]) % (10**9+7)
	lista.append(dp[n])
for i in lista:
	print(i)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
lista = []
for i in range(int(eval(input()))):
	n = int(eval(input()))
	dp = [0, 0, 1] + [0] * (n-2)
	fib = [0, 1, 1] + [0] * (n-3)
	for i in range(3, n):
		fib[i] = (fib[i-1] + fib[i-2]) % (10**9+7)
	for i in range(3, n+1):
		dp[i] = (dp[i-1] + dp[i-2] + fib[i-1]) % (10**9+7)
	lista.append(dp[n])
for i in lista:
	print(i)


t=int(input())
for i in range(0,t):
	n = int(input())
	d=[]
	d.append(0)
	d.append(0)
	d.append(1)
	f=[]
	f.append(0)
	f.append(1)
	f.append(1)
	for i in range(3, n):
		f.append((f[i-1] + f[i-2])%1000000007)
	for i in range(3, n+1):
		d.append((d[i-1] + d[i-2] + f[i-1]) % 1000000007)
	print(d[n])
	


import sys


def compute(count, nmax):
	count_1 = [-1 for i in range(nmax)]
	count_1[0] = 0
	count_1[1] = 1
	count_1[2] = 3
	power = 4
	for i in range(3, nmax):
		count_1[i] = (count_1[i-1] + count_1[i-2] + power) % 1000000007
		power = (power * 2) % 1000000007
	count[0] = 0
	count[1] = 1
	count[2] = 2
	power = 2
	for i in range(3, nmax):
		count[i] = (count[i - 1] + count[i - 2] - count_1[i - 3] + power ) % 1000000007
		power = (power * 2) % 1000000007

def main():
	t = int(sys.stdin.readline())
	cases = []
	for n in range(t):
		cases.append(int(sys.stdin.readline()))
	casemax = max(cases)
	count = [-1 for i in range(casemax)]

	compute(count, casemax)
	for case in cases:
		print((count[case - 1]))

if __name__ == "__main__":
	main()