def fibonacciwrapper(line):
    l1 = 1000000007
    l2 = 2000000016
    l3 = 329616
    if line >= l3:
        line = line % l3
    tmp = _fib(line, l2)[0]
    if tmp >= l2:
        tmp %= l2
    tmp2 = _fib(tmp, l1)[0]
    if tmp2 >= l1:
        tmp2 %= l1
    print (tmp2)
def _fib(n, m):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2, m)
        if b>= m:
            b %= m
        c = a * (2 * b - a)
        if c >= m or c < 0:
            c %= m
        d = (b * b + a * a)
        if d >= m:
            d %= m
        if n & 1:
            return (d, c + d)
        else:
            return (c, d)
def solV1():
    import sys
    inputL = list(map(int, sys.stdin.readlines()[1:]))
    map(fibonacciwrapper, inputL)
if __name__ == '__main__':
    solV1()