Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\) và số nguyên dương \(k(1≤k≤n)\).

Một dãy con của 𝐴 gồm các số hạng \(a_{i_1 }, a_{i_2 }, …., a_{i_m }\) thoả mãn:

• \(1≤i_1<i_2<⋯<i_m\)

• \(i_2-i_1≥k ;i_3-i_2≥k;…;i_m-i_(m-1)≥k.\)

Thì dãy con trên được gọi là dãy có độ đẹp k.

Dãy con có một số hạng cũng được gọi là dãy con có độ đẹp k.

Gọi trọng số của dãy con \(a_{i_1 }, a_{i_2 }, …., a_{i_m }\) có độ đẹp là \(k\) bằng \(a_{i_1 }+ a_{i_2 }+ … + a_{i_m }\)

Yêu cầu: Tính tổng trọng số của tất cả các dãy con độ đẹp \(𝑘\) của dãy \(𝐴\).

Input

• Dòng 1 ghi hai số nguyên dương \(n,k (1 ≤ k < n ≤ 10^6 ).\)

• Dòng 2 ghi \(𝑛\) số nguyên \(a_1,a_2,…,a_n (a_i≤10^6).\)

Output

• Ghi một số nguyên là số dư của kết quả tìm được chia cho \(10^9+7\).

Ràng buộc

• Subtask 1: Có 25% số test ứng với \(k = 1,n ≤ 20;\)

• Subtask 2: Có 25% số test ứng với \(n ≤ 20;\)

• Subtask 3: Có 50% số test ứng với \(20 < n ≤ 10^6\)

Sample Input

1 3 3 4

Sample Output

27