You are given a 1-D array of size \(N\). You are required to create a square matrix of size \( \sqrt{N} \times \sqrt{N} \). The creation of a matrix is done by selecting first \( \sqrt{N} \) elements from the array for the first row of the matrix, then next \( \sqrt{N} \) elements for the second row and this goes up to for \( {(\sqrt{N})}^{th} \) row. There is also a possibility that some elements of the array may not be used for creating a square matrix. You are also given an integer \(K\), you have to circularly right shift the \( 1-D \) array by one for \(K\) times and for every shifting, a new \( 1-D \) array or better say new square matrix is formed. After shifting for \(K\) times, you come up with total \( K + 1 \) square matrices.

For example, if the given array is \( (2,3,4,5,6) \) and the value of \(K\) is 2. The size of the square matrix is \( \sqrt{5} \) i.e. \( 2 * 2 \).

An initial square matrix is defined as \( m0[0][0]=2, m0[0][1]=3, m0[1][0]=4, m0[1][1]=5\).

For \( K = 2 \), we need to circularly right shift array by one twice. Therefore, after the first circular right shift, the array becomes \( (6,2,3,4,5) \) and the new square matrix \( m1 \) is defined as \( m1[0][0]=6, m1[0][1]=2, m1[1][0]=3, m1[1][1]=4\).

Similarly, after the second circular right shift, the array becomes \( (5,6,2,3,4) \) and the square matrix \( m2 \) is defined as \( m2[0][0]=5, m2[0][1]=6, m2[1][0]=2, m2[1][1]=3 \).

Now, you are required to determine the multiplication of these \( (K + 1) \) matrices and print the sum of resultant elements of the square matrix.

Since answer can be large, print it modulo \( 10^9+7 \).

Input format

First line: Two integers \(K\) and \(N\) denoting the number of circular right shifts and the size of the 1-D array respectively
Next line: \(N\) space-separated integers denoting elements of \( 1-D \) array

Output format

Print an integer that denotes the sum of all the elements of the resultant matrix. Since answer may be large, print it modulo \( 10^9+7 \).

Constraints

\( 1 \leq N \leq 1000 \)

\( 0 \leq A[i] \leq 10^9 \)

\( 1 \leq K \leq 10^{15} \)