递推数

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

已知A(0) = 0 , A(1) = 1 , A(n) = 3 * A(n-1) + A(n-2) (n ≥ 2)

A(A(A(A(N)))) Mod (1e9 + 7)

Input

第一行一个整数 T (T ≤ 10000) 代表数据组数

每组数据占一行,一个整数 n (1 ≤ n ≤ 1e12)

Output

对于每组测试数据输出一个整数。

Sample Input

4
1
23574
27870
913

Sample Output

1
0
0
1

Source

buaads

Manager

Information
Solved Number61
Submit Number134
Problem Tags
brute force
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel