Dirichlet Convolution Power Sum

We are given an arithmetic function \(f\) defined on the positive integers. Define its Dirichlet convolution power \(f^n\) recursively as follows:

[ f^n = \begin{cases} f & n=1\ f^{n-1}* f & n\ge 2 \end{cases} ]

Here, the Dirichlet convolution \( * \) between two arithmetic functions \(f\) and \(g\) is defined by

[ (f*g)(n)=\sum_{d|n} f(d),g\Big(\frac{n}{d}\Big) ,\quad \text{for } n\ge 1. ]

For given positive integers \(n\) and \(m\), and given values of \(f(1),f(2),\dots,f(n)\), define an arithmetic function \(g\) by:

[ g = f + f^2 + \cdots + f^m, ]

that is, for every \(k\) (with \(1\le k \le n\)),

[ g(k)=\sum_{i=1}^{m}{f^i(k)} \quad (\bmod;10^9+7). ]

In order to limit the output size, you are only required to output the value

[ \bigoplus_{k=1}^{n}(g(k) \bmod (10^9+7)), ]

where \(\oplus\) denotes the bitwise XOR operation.

Input: The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers, where the \(i\)th integer is \(f(i)\). It is guaranteed that \(n\) and \(m\) are positive integers and that all numbers in the input are valid.

Output: Output a single integer, which is the XOR of all \(g(1),g(2),\dots,g(n)\) modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space. The second line contains \(n\) integers \(f(1), f(2), \dots, f(n)\) separated by spaces.

outputFormat

Output a single integer: the value of \(\bigoplus_{k=1}^{n} (g(k) \bmod (10^9+7))\).

sample

3 2
1 1 1

2