Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMYT - Hành trình đến đảo dừa

) 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à Ai

Giới hạn

  • 1 ≤ N ≤ 109
  • 1 ≤ K ≤ 50 và K < N.
  • 1 ≤ Ai ≤ 109
  • 30% số test có N ≤ 100000

 

Output

  • Ghi ra kết quả theo modulo 1000000007 (109 + 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

Được gửi lên bởi:VOJ Team
Ngày:2013-06-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:VM13 - Lê Yên Thanh

hide comments
2019-12-23 12:12:27
Có ai giống tôi không? Nhớ dùng định lí Fermat nhỏ mà quên reset ma trận khi nhân! Thật là đắng mà :(( (10đ)
2019-07-28 10:59:26
Lại quên mod . Ai làm nhớ để mod mọi nơi nha. Chú ý sử dụng định lý fermat để xử lý số mũ.
Lời khuyên chân thành từ một bạn nam đẹp trai không tiện nói tên :)))
2019-05-16 10:57:05
nếu bạn 10d còn quan tâm, vì (a^b)%MOD khác hoàn toàn (a^(b%MOD))%MOD.
2018-07-25 07:57:29
.

Last edit: 2018-07-25 07:57:41
2018-02-20 11:13:43
Em ko dùng fermat và bị 10đ ! Tại sao vậy ạ ?
2017-09-30 06:56:25
{dinh truong lam}

cái fermat chết tiệt làm mất cả buổi sáng mới 100d
2015-11-11 16:15:57 lucky++


Last edit: 2015-11-19 06:14:59
2015-10-27 09:27:31 Prismatic
one hit :))
2014-07-02 02:37:02 Tây Cuồng
Cảm ơn anh (chị) Bit
2013-07-12 12:52:27 an IM3 Ex-Member of Bit
http://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_nh%E1%BB%8F_Fermat
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.