mod = (len('abcdefghij') ** len('abcdefghi')) + len('abcdefg') # 1000000007 def add(a, b): while b: carry = a & b a = a ^ b b = carry << 1 a %= mod b %= mod return a % mod def multiply(a, b): result = 0 while b: if b & 1: result = add(result, a) a = add(a, a) b >>= 1 return result % mod def mat_mult(m1, m2): a = add(multiply(m1[0][0], m2[0][0]), multiply(m1[0][1], m2[1][0])) b = add(multiply(m1[0][0], m2[0][1]), multiply(m1[0][1], m2[1][1])) c = add(multiply(m1[1][0], m2[0][0]), multiply(m1[1][1], m2[1][0])) d = add(multiply(m1[1][0], m2[0][1]), multiply(m1[1][1], m2[1][1])) return [[a % mod, b % mod], [c % mod, d % mod]] def mat_pow(mat, power): result = [[1, 0], [0, 1]] # Identity matrix while power: if power & 1: result = mat_mult(result, mat) mat = mat_mult(mat, mat) power >>= 1 return result def compute_lucas(n): if n == 0: return 2 % mod one = len('a') # 1 two = len('ab') # 2 zero = len('') # 0 mat = [[one, one], [one, zero]] power = n - one mat_result = mat_pow(mat, power) a = multiply(mat_result[0][0], one) b = multiply(mat_result[0][1], two) res = add(a, b) return res % mod T = int(input()) for _ in range(T): n = int(input()) print(compute_lucas(n))