Giải bài trực tuyến

) nhưng khổ nỗi vương quốc dừa dùng điện năng lượng mặt trời nên không có đủ điện để chạy siêu máy tính được. Thế là giờ chỉ còn mỗi cái Laptop Pentium 3 800Mhz là có thể dùng được. Bạn là một nhà lập trình viên siêu hạng, hãy giúp yenthanh132 và chứng tỏ rằng Laptop cùi tới mấy mà biết sử dụng thì cũng có thể làm nên chuyện :)

Yêu cầu:

- Cho số N, K và dãy số a[1], a[2],... , a[K] - số đảo dừa trong vương quốc qua K năm đầu
- Với i>K ta có a[i] = a[i-1] * a[i-2] * a[i-3] * ... * a[i-K];
- Tính a[N], do số lượng hòn đảo rất lớn nên yenthanh132 chỉ yêu cầu bạn tính phần dư của kết quả khi chia cho số 1000000007 ( = 10^9 + 7). Tức là tính a[N] % 1000000007

Lưu ý: Những đường dẫn đến bài tập bên ngoài chỉ mang tính chất tham khảo cho vui, không liên quan đến bài này.

 

Input

• Dòng đầu tiên gồm hai số nguyên dương N, K.
• Dòng thứ hai ghi K số nguyên dương, số thứ i của dãy số là A_i

Giới hạn

• 1 ≤ N ≤ 10⁹
• 1 ≤ K ≤ 50 và K < N.
• 1 ≤ A_i ≤ 10⁹
• 30% số test có N ≤ 100000

 

Output

• Ghi ra kết quả theo modulo 1000000007 (10⁹ + 7).

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:

7 3

1 2 3

Output:

139968