There are coins of $2$ different denominations in Crazyland, $1$-cent coins and $2$-cent coins. They have two faces - heads and tails.

Your task is to find out the the number of ways to create a linear arrangement of these coins so that their sum is $N$ cents. The only condition on the linear arrangement is that the first coin in the arrangement should always have heads up. All other coins could have either tails or heads up. 
        
Take $N = 2$ as an example. The possible arrangements are $(1H, 1H)$, $(2H)$, $(1H, 1T)$, where $H$ is heads and $T$ is tails. Therefore there are $3$ possible arrangements that sum up to $2$-cents.

Note: While counting make sure to differentiate between heads and tails.
    
------  Input ------
First line contains a single integer - $T$, the number of test cases.
$T$ lines follow, each containing a single integer $N$, the required sum.
    
------  Constraints ------
$0 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{9}$
    
------  Output  ------
For each case the output should be a single integer representing the number of such arrangements possible. As the answer can be very large, print it modulo $10^{9} + 7$.
    
----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
1
3
8

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Matrices

Mathematics


Solutions:
mod = 10 ** 9 + 7

def mult(mat1, mat2):
	mat3 = [[0, 0], [0, 0]]
	mat3[0][0] = (mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]) % mod
	mat3[0][1] = (mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]) % mod
	mat3[1][0] = (mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]) % mod
	mat3[1][1] = (mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]) % mod
	return mat3

def power(mat, n):
	if n == 0:
		a = [[1, 0], [0, 1]]
		return a
	if n == 1:
		return mat
	ans = power(mat, int(n // 2))
	if n & 1:
		return mult(mat, mult(ans, ans))
	else:
		return mult(ans, ans)
t = int(input())
for i in range(t):
	n = int(input())
	mat = [[2, 2], [1, 0]]
	f1 = 1
	f2 = 3
	if n == 1:
		print(1)
	elif n == 2:
		print(3)
	else:
		mat = power(mat, n - 2)
		ans = mat[0][0] * f2 + mat[0][1] * f1
		ans = ans % 1000000007
		print(ans)


mod = 10 ** 9 + 7

def snek(m1, m2):
	m3 = [[0, 0], [0, 0]]
	m3[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % mod
	m3[0][1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % mod
	m3[1][0] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % mod
	m3[1][1] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % mod
	return m3

def snek2(m, n):
	if n == 0:
		a = [[1, 0], [0, 1]]
		return a
	if n == 1:
		return m
	ans = snek2(m, int(n // 2))
	if n & 1:
		return snek(m, snek(ans, ans))
	else:
		return snek(ans, ans)
t = int(input())
for i in range(t):
	n = int(input())
	m = [[2, 2], [1, 0]]
	f1 = 1
	f2 = 3
	if n == 1:
		print(1)
	elif n == 2:
		print(3)
	else:
		m = snek2(m, n - 2)
		ans = m[0][0] * f2 + m[0][1] * f1
		ans %= 1000000007
		print(ans)


from sys import stdin, stdout
from math import ceil
import numpy as np
from numpy.linalg import matrix_power
mod = 10 ** 9 + 7

def mul(m, l):
	c1 = m[0][0]
	c2 = m[0][1]
	c3 = m[1][0]
	c4 = m[1][1]
	a1 = l[0][0]
	a2 = l[0][1]
	a3 = l[1][0]
	a4 = l[1][1]
	a = (c1 % mod * a1 % mod % mod + c2 % mod * a3 % mod % mod) % mod
	b = (c1 % mod * a2 % mod % mod + c2 % mod * a4 % mod % mod) % mod
	c = (c3 % mod * a1 % mod % mod + c4 % mod * a3 % mod % mod) % mod
	d = (c3 % mod * a2 % mod % mod + c4 % mod * a4 % mod % mod) % mod
	return [[a, b], [c, d]]

def fast_matrix(f, p):
	if p == 1:
		return f
	z = fast_matrix(f, p // 2)
	if p % 2 == 0:
		return mul(z, z)
	else:
		return mul(mul(z, z), f)

def solve():
	mod = 10 ** 9 + 7
	for _ in range(int(input())):
		f = [[2, 1], [2, 0]]
		yo = [[1, 3]]
		n = int(input())
		if n > 2:
			m = fast_matrix(f, n - 2)
			c1 = m[0][0]
			c3 = m[0][1]
			c2 = m[1][0]
			c4 = m[1][1]
			print((3 * c1 + c2) % mod)
		else:
			if n == 1:
				ans = 1
			elif n == 2:
				ans = 3
			print(ans)
solve()


mod = 10 ** 9 + 7

def mul(m, l):
	c1 = m[0][0]
	c2 = m[0][1]
	c3 = m[1][0]
	c4 = m[1][1]
	a1 = l[0][0]
	a2 = l[0][1]
	a3 = l[1][0]
	a4 = l[1][1]
	a = (c1 % mod * a1 % mod % mod + c2 % mod * a3 % mod % mod) % mod
	b = (c1 % mod * a2 % mod % mod + c2 % mod * a4 % mod % mod) % mod
	c = (c3 % mod * a1 % mod % mod + c4 % mod * a3 % mod % mod) % mod
	d = (c3 % mod * a2 % mod % mod + c4 % mod * a4 % mod % mod) % mod
	return [[a, b], [c, d]]

def fast_matrix(l, p):
	if p == 1:
		return l
	z = fast_matrix(l, p // 2)
	if p % 2 == 0:
		return mul(z, z)
	else:
		return mul(mul(z, z), l)
t = int(input())
for i in range(t):
	l = [[2, 1], [2, 0]]
	yo = [[1, 3]]
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(3)
	else:
		z = fast_matrix(l, n - 2)
		c1 = z[0][0]
		c3 = z[0][1]
		c2 = z[1][0]
		c4 = z[1][1]
		print((3 * c1 + c2) % mod)