Câu 2 đề thi thử HSG L9 Quỳnh Lưu

Trong cuộc thi "Olympic Huyện Quỳnh Lưu", ban giám khảo chuẩn bị một màn hình lớn, người ta cho lần lượt xuất hiện các số của một dãy số nguyên dương ~a_1, a_2, ..., a_n~ và cứ lặp lại như thế không ngừng (nghĩa là đầu tiên a1 xuất hiện, rồi đến ~a_2, a_3, ..., a_n, a_1, a_2, ....~).

Yêu cầu:

Bạn hãy giúp ban tổ chức tính tổng ~k~ số liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên xuất hiện thứ ~p~.

Dữ liệu:

• Dòng thứ nhất ghi số nguyên dương ~n, k, p~.
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ 10^9~)

  Kết quả:

Một số nguyên duy nhất là kết quả bài toán chia lấy dư cho ~10^9+7~.

Ví dụ:

Input

5 7 6
2 3 6 7 9

Output

32

Giải thích

7 số nguyên liên tiếp xuất hiện trên màn hình bắt đầu từ số xuất hiện thứ 6 là: 2 3 6 7 9 2 3 kết quả: (2 + 3 + 6 + 7 + 9 + 2 + 3) mod 1000000007 = 32

Giới hạn

• Có 40% số test ứng với 40% số điểm thỏa mãn ~n ≤ 10^3~; ~p = 1; k ≤ n~;
• Có 30% số test ứng với 30% số điểm thỏa mãn ~n ≤ 10^3~; ~p, k ≤ 10^6~;
• Có 30% số test ứng với 30% số điểm thỏa mãn ~n ≤ 10^6~; ~p, k ≤ 10^{18}~;