P1998 DGF Geometric Sum

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))$.

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

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