Shil has an array of N elements A1 , A2, ... ,AN . He also has an integer K. He wants to find out value of Square Sum for every i from 1 to N-K+1.
The value of Square Sum for certain i is defined as Σ1≤ j ≤ K (j^2 Ai+j-1).

Input:
First line of input consists of two integers N and K. Next line consists of N integers A1 , A2, ... ,AN.

Output:
Output N-K+1 integers where ith integer corresponds to Square Sum of i. Print Square Sum modulus 10^9+7.

Constraints:
1≤ K ≤ N ≤ 10^6
1≤ Ai ≤ 10^9

SAMPLE INPUT
6 3
6 9 10 10 4 6

SAMPLE OUTPUT
132 139 86 80

见题面

见题面