Tèo và Tý vào Trung tâm thương mại để mua đồ. Khi vào siêu thị, 2 bạn thấy một thang cuốn và ở các bậc thang được đánh số thứ tự từ 1 đền n, trên mỗi bậc thang có ghi một số nguyên dương. Tuy nhiên, do thang cuốn liên tục lặp lại nên các bậc thang cũng lặp lại theo đúng trật tự. Tý đố Tèo tính tổng của m bậc thang liên tiếp bắt đầu từ bậc thang thứ k, nếu Tèo tính đúng sẽ được Tý mua cho một món quà trong Trung tâm thương mại.

Hãy giúp Tèo tính toán tổng này để nhận được quà từ Tý.

Yêu cầu: Nhập vào từ bàn phím

• Dòng thứ nhất chứa các số nguyên dương n, m, k cách nhau bởi dấu cách (~m, k ≤ 10^8; n ≤ 10^6~)

• Và dòng thứ 2 chứa n số nguyên dương ai, a2, a3, ..., an cách nhau bởi dấu cách là các số ghi trên các bậc thang từ bậc thứ nhất đến bậc thứ n của thang cuốn. (~1 ≤ ai ≤ 10^9~)

Kết quả: In ra màn hình số nguyên dương duy nhất là kết quả bài toán chia lấy dư cho ~10^9+ 7~

Input:

6 8 3
3 4 2 1 4 5

Output:

22

Giải thích: 8 số nguyên liên tiếp bắt đầu từ vị trí số 3 là: 2 1 4 5 3 4 2 1

Kết quả: (2 + 1 + 4 + 5 + 3 + 4 + 2 + 1) mod 1000000007 = 22