THỰC HÀNH

Cho dãy số (a_n) xác định bởi:

• a₁ = 1; a₂ = 2; a₃ = 3
• a_n = a_n-3 – 2a_n-2 + 3a_n-1 với  n ≥ 4

Yêu cầu: Cho số m và m số nguyên dương n₁, n₂, …, n_m. Tính a_n1, a_n2, …, a_nm.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương m.
• Dòng hai chứa m số nguyên dương n₁, n₂, …, n_m. Hai số liên tiếp được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

Một dòng duy nhất chứa m số nguyên là phần dư của các số a_n1, a_n2, …, a_nm khi chia cho 10⁹ + 7. Hai số liên tiếp cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
2
5 15

Dữ liệu ra:
14 65657

Giới hạn: 1 ≤ m ≤ 1000; 0 ≤ n_i ≤ 10¹⁸;