for _ in range(int(eval(input()))):

	n=int(eval(input()))

	print((sum([n**j*[[0,765144583,346175634,347662323,5655049,184117322,927321758,444014759,542573865,237315285,417297686,471090892,183023413,660103155,727008098,869418286],[539588932,729548371,700407153,404391958,962779130,184117322,927321758,444014759,542573865,237315285,417297686,471090892,183023413,660103155,727008098,869418286]][n&1][j]for j in range(16)])%(10**9+7)))
t,*n=list(map(int,open(0)))

for k in n:print((sum(k**j*[0,765144583,346175634,347662323,5655049,184117322,927321758,444014759,542573865,237315285,417297686,471090892,183023413,660103155,727008098,869418286,539588932,729548371,700407153,404391958,962779130,184117322,927321758,444014759,542573865,237315285,417297686,471090892,183023413,660103155,727008098,869418286][(k&1)*16+j]for j in range(16))%(10**9+7)))
for _ in range(int(eval(input()))):
    n = int(eval(input()))
    print(
        (
            sum(
                [
                    n**j
                    * [
                        [
                            0,
                            765144583,
                            346175634,
                            347662323,
                            5655049,
                            184117322,
                            927321758,
                            444014759,
                            542573865,
                            237315285,
                            417297686,
                            471090892,
                            183023413,
                            660103155,
                            727008098,
                            869418286,
                        ],
                        [
                            539588932,
                            729548371,
                            700407153,
                            404391958,
                            962779130,
                            184117322,
                            927321758,
                            444014759,
                            542573865,
                            237315285,
                            417297686,
                            471090892,
                            183023413,
                            660103155,
                            727008098,
                            869418286,
                        ],
                    ][n & 1][j]
                    for j in range(16)
                ]
            )
            % (10**9 + 7)
        )
    )

t, *n = list(map(int, open(0)))
for k in n:
    print(
        (
            sum(
                k**j
                * [
                    0,
                    765144583,
                    346175634,
                    347662323,
                    5655049,
                    184117322,
                    927321758,
                    444014759,
                    542573865,
                    237315285,
                    417297686,
                    471090892,
                    183023413,
                    660103155,
                    727008098,
                    869418286,
                    539588932,
                    729548371,
                    700407153,
                    404391958,
                    962779130,
                    184117322,
                    927321758,
                    444014759,
                    542573865,
                    237315285,
                    417297686,
                    471090892,
                    183023413,
                    660103155,
                    727008098,
                    869418286,
                ][(k & 1) * 16 + j]
                for j in range(16)
            )
            % (10**9 + 7)
        )
    )

-for _ in range(int(eval(input()))): -    n = int(eval(input())) +t, *n = list(map(int, open(0))) +for k in n: -                [ -                    n**j -                    * [ -                        [ -                            0, -                            765144583, -                            346175634, -                            347662323, -                            5655049, -                            184117322, -                            927321758, -                            444014759, -                            542573865, -                            237315285, -                            417297686, -                            471090892, -                            183023413, -                            660103155, -                            727008098, -                            869418286, -                        ], -                        [ -                            539588932, -                            729548371, -                            700407153, -                            404391958, -                            962779130, -                            184117322, -                            927321758, -                            444014759, -                            542573865, -                            237315285, -                            417297686, -                            471090892, -                            183023413, -                            660103155, -                            727008098, -                            869418286, -                        ], -                    ][n & 1][j] -                    for j in range(16) -                ] +                k**j +                * [ +                    0, +                    765144583, +                    346175634, +                    347662323, +                    5655049, +                    184117322, +                    927321758, +                    444014759, +                    542573865, +                    237315285, +                    417297686, +                    471090892, +                    183023413, +                    660103155, +                    727008098, +                    869418286, +                    539588932, +                    729548371, +                    700407153, +                    404391958, +                    962779130, +                    184117322, +                    927321758, +                    444014759, +                    542573865, +                    237315285, +                    417297686, +                    471090892, +                    183023413, +                    660103155, +                    727008098, +                    869418286, +                ][(k & 1) * 16 + j] +                for j in range(16)