P17622 [qaswed12 OI R1] Function

定义函数 $f$ 满足： $$f(x)=\sum\limits_{i=0}^x{x\choose i}(-1)^{\gcd(x,i)}.$$ 特别的，$\gcd(x,0)=x$。 --- 给定一个长度为 $n$ 的序列 $A$。 有 $m$ 次操作，操作分为两种： 1. `1 l r k`，表示 $\forall i\in[l,r],A_i\gets A_i+k$。 2. `2 l r`，表示查询 $\sum\limits_{i=l}^r f(A_i)$。 答案可能会比较大，请对 $10^9+7$ 取模。

第一行，两个正整数 $n,m$。 第二行，$n$ 个整数，表示序列 $A$。 接下来 $m$ 行，每一行表示一个操作，输入方式见题目描述。

对于每个操作二，输出一行，一个非负整数表示答案。

### 样例解释 第一次询问的实际答案为 $-38.$ ### 数据范围与说明 本题输入输出量较大，请使用较快的输入输出方式。 **本题开启捆绑测试。** |子任务编号|$n,m \le$|$A_i,k \le$|特殊性质|分值| |:-------:|:-------:|:------:|:------:|:----:| |$1$ |$10^2$ |$50$|无 |$10$ | |$2$ |$5\times 10^3$ |$10^3$|^ |$15$ | |$3$ |$10^5$ |$10^5$|$\text A$ |$15$ | |$4$ |^ |^|$\text B$ |$15$ | |$5$ |^ |^|无 |$20$ | |$6$ |$10^6$ |$10^6$|^ |$25$ | 特殊性质 $\text A$：保证对于每次操作，满足 $l=1,r=n$。 特殊性质 $\text B$：保证对于每次操作一，满足 $k=1$。 对于 $100\%$ 的数据，满足 $1\le n,m,A_i,k \le 10^6$，$1 \le l \le r \le n$。