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}$