Biết \(F_n\) = Số nguyên dương thứ \(n\) không chia hết cho \(2\).

Hãy tính \(S_n = F_1 + F_2 + ... + F_n\).

Input

• Số nguyên dương \(T ( T \leq 100)\) - số test.
• Mỗi test trên \(1\) dòng , một số nguyên dương \(n (n \leq 10^{16})\).

Output

• Mỗi test trên một dòng, \(S_n \% (10^9+7)\).

Example

2
2
1 

4
1