Description

Given a number-theoretic function $f$, define $f^n$ as:

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

Here $*$ denotes the Dirichlet convolution.

For positive integers $n, m$, let the number-theoretic function $g=f+f^2+\cdots+f^m$. Compute $g(1), g(2), \cdots, g(n)$, and take the answers modulo $10^9+7$.

To control the output size, it is sufficient to output the value of $\bigoplus_{k=1}^n(g(k)\bmod (10^9+7))$.

Input Format

The first line contains two positive integers $n, m$.

The second line contains $n$ non-negative integers, representing $f(1), f(2), \cdots, f(n)$ in order.

Output Format

Output one non-negative integer on a single line, representing $\bigoplus_{k=1}^n(g(k)\bmod (10^9+7))$.

10 10
1 1 4 5 1 4 1 9 1 9

1864

Hint

Constraints: For all testdata, it is guaranteed that $1\le n\le 10^6$, $1\le m\le 10^9$, and for $1\le i\le n$, always $0\le f(i)\le 10^9$.

In particular, $f(1)=1$, $f(2)\ne 0$.

For Sample 1, the first $10$ terms of $g$ are $10, 55, 220, 440, 55, 1540, 55, 2475, 2695, 825$.

The time limit is 4 times that of the "std". Please use fast I/O.

Translated by ChatGPT 5