THỰC HÀNH

Cho số nguyên dương k và hai bộ k số nguyên α₁, α₂, …, α_k; c₁, c₂, …, c_k.

Dãy số (a_n) cho bởi:

• a_i = c_i với 1 ≤ i ≤ k
• a_i = α₁a_{i – k} + α₂a_{i – k + 1} + … + α_ka_{i – 1} với i > k

Yêu cầu: Cho biết k_, α₁, α₂, …, α_k; c₁, c₂, …, c_k 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 hai số nguyên dương k, m.
• Dòng hai chứa α₁, α₂, …, α_k.
• Dòng ba chứa c₁, c₂, …, c_k.
• Dòng 4 chứa n₁, n₂, …, n_m.

Hai số liên tiếp trên một dòng đượ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 2
1 1
1 1
10 45

Dữ liệu ra:
55 134903163

Giải thích: dãy số (a_n) chính là dãy số Fibonacci.

Giới hạn: 1 ≤ k ≤ 10; 0 ≤ α_i ≤ 10⁹; 0 ≤ c_i ≤ 10⁹; 1 ≤ m ≤ 100; 0 ≤ n_i ≤ 10¹⁸;