题目描述

给定数论函数 $f$，定义 $f^n$ 为：

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

其中 $*$ 是 Dirichlet 卷积。

对于正整数 $n,m$，记数论函数 $g=f+f^2+\cdots+f^m$，请求出 $g(1),g(2),\cdots,g(n)$，答案对 $10^9+7$ 取模。

为控制输出量，只需输出 $\bigoplus_{k=1}^n(g(k)\bmod (10^9+7))$ 的值即可。

输入格式

第一行两个正整数 $n,m$。

第二行共 $n$ 个自然数，顺次代表 $f(1),f(2),\cdots,f(n)$。

输出格式

一行一个自然数，代表 $\bigoplus_{k=1}^n(g(k)\bmod (10^9+7))$。

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

1864

提示

对于所有数据，保证 $1\le n\le 10^6,1\le m\le 10^9$，且对于 $1\le i\le n$，恒有 $0\le f(i)\le 10^9$。

特别地，$f(1)=1,f(2)\neq 0$。

对于样例一，$g$ 的前 $10$ 项依次为 $10, 55, 220, 440, 55, 1540, 55, 2475,2695,825$。

时限为 std 的 4 倍，请使用较快的读入方式。