Shil has an array of N elements A₁ , A₂, ... ,A_N . 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² A_i+j-1).

Input:
First line of input consists of two integers N and K. Next line consists of N integers A₁ , A₂, ... ,A_N.

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

Constraints:

• 1≤ K ≤ N ≤ 10⁶
• 1≤ A_i ≤ 10⁹