Total path verion II (public version)

Bài này có 3 version và đây là version II.

Điểm khác của version II với version I là bài này có T test và giới hạn n lớn hơn.

Bạn được cho 1 hình chóp tứ giác A1A2A3A4 với đỉnh A4 là đỉnh của hình chóp tứ giác và 3 đỉnh A1, A2, A3 là đáy. Chú kiến Alex ban đầu đứng ở đỉnh A4 . Chú kiến này rất hiếu động và không thể đứng im 1 chỗ tại mỗi thời điểm, do đó với mỗi thời điểm chú kiến phải di chuyển tới 1 trong các đỉnh kề với đỉnh mà chú đang đứng thông qua các cạnh của hình chóp tứ giác. Do chú kiến di chuyển liên tục như vậy nên thầy Otto muốn biết rằng sau n thời điểm thì có thể có bao nhiêu con đường khác nhau tạo ra sao cho chú kiến Alex ban đầu từ đỉnh A4, di chuyển qua n cạnh và kết thúc ở đỉnh A4.

Ví dụ:

• Với n = 2 thì ta sẽ có 3 con đường có thể tạo ra: 
  • A4 - A1 - A4.
  • A4 - A2 - A4.
  • A4 - A3 - A4.

[Đầu vào/Đầu ra]:

• Giới hạn thời gian]: 1s với C++, 6s với Java & C#, 8s với Python,Go,Js.
• [Đầu vào]: Số tự nhiên T (1 ≤ T ≤ 105) biểu thị số test mà thầy Otto muốn tính.
• [Đầu vào]: Array of Integers A gồm T số, mỗi số Ti (1 ≤ Ti ≤ 1018) biểu thị số cạnh mà chú kiến Alex phải đi qua tương ứng với test i.
• [Đầu ra]: Arrays of Integers, gồm T số, mỗi số biểu thị số lượng con đường có thể tạo ra theo modulo 109+7.

[Mô tả các test]:

• Test 1 → 5: 1 ≤ T ≤ 10, 1 ≤ Ai ≤ 103. 
• Test 6 → 10: 1 ≤ T ≤ 103, 1 ≤ Ai ≤ 103. 
• Test 11 → 15: 103 ≤ T ≤ 105 , 1 ≤ Ai ≤ 106. 
• Test 16 → 20: 1 ≤ T ≤ 105 , 1 ≤ Ai ≤ 109.
• Test 21 → 25: 1 ≤ T ≤ 105 , 1 ≤ Ai ≤ 1018.
• Test 26: T = 105.