Cô Q rất yêu thích toán học nên đã đố các bạn 1 bài toán như sau.

Cho hai số nguyên k và n. Ta định nghĩa công thức mở rộng của dãy Fibonacci như sau (gọi là k-bonacci):

• F^(k)₁ = a₁, F^(k)₂ = a₂, ..., F^(k)_k = a_k.
  Với a₁, a₂, ..., a_k là các số tự nhiên.

• Với n > k:
  F^(k)_n = F^(k)_n-1 + F^(k)_n-2 + … + F^(k)_n-k.

Ta định nghĩa tổng của n số k-bonacci đầu tiên như sau:

• S^(k)(n) = F^(k)₁ + F^(k)₂ + … + F^(k)_n.

Yêu cầu: Bạn hãy tính S^(k)(n) mod (~10^{9} + 7~).

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên k và n.
• Dòng thứ hai gồm k số tự nhiên a₁, a₂, ..., a_k.

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả của phép tính S^(k)(n) mod (~10^{9} + 7~).

Input:

3 4
1 1 2

Output:

8

Giới hạn:

• ~2 \le k \le 100~, ~1 \le n \le 10^{18}~.
• ~1 \le a_1, a_2, ..., a_k \le 10^9~