题目描述

有一天，玥玥在电视上，看到了一种神奇的数字变换。

这种变换是这样的： 首先我们拿到一个正整数，然后对它分别进行以下分解：

1. 分解它的质因数，数一数其质因数的指数，如果有一个质因数的指数 ≥ 2 ， 写下 0；否则，若有奇数个质因数，写下 −1 ，否则写下 1。
2. 分解其所有正约数，写下其约数个数以及约数总和。 显然，对于每一个数 𝑥，经过变换后将得到 3 个整数。

玥玥试了试，发现他算出了正确的答案，他太开心了！

然而，很不幸，这一切被玥玥的老师看见了。老师总算是找到了给玥玥出题的机会，于是在第二天，老师给玥玥留了一道《好》题。 老师给玥玥了 𝑛 个正整数，排成一排。老师让玥玥仔细看看这个序列（名字叫 𝑎），然后告诉了玥玥他会问 𝑞 个问题。每一个问题中，老师给出两个数 𝑙, 𝑟，让玥玥算出数字 𝑥 的答案，其中$x=\prod_{i=l}^{r}a_i$ 。

“老师，这个数（指 𝑥𝑥）太大了怎么办？”

“没关系，你只需要告诉我答案对 $10^9 + 7$ 取模的结果就行了（完全理解成了答案太大）。

实在不行的话，可以请别人帮忙哦。”这下可把玥玥难住了。

她请班上 OI 最强的你来帮他解决这个问题，毕竟，这可 能会给她加不少德育分啊！ 老师比较善良，所以每一次回答问题时，只需要回答答案中的第 type问就可以 （$1 ≤ type ≤ 3）$。注意，这里的输出 𝑥 的答案指的是输出 𝑥 经过上述变换得到的 3 个整数中的第 type 个。

由于老师的问题是一个一个问的，所以本题强制在线。

输入格式

第一行三个整数 𝑛, 𝑞,type ，其中 type 表示询问种类。 第二行 𝑛 个整数，第 𝑖 个整数代表 $𝑎_𝑖$。

后面 𝑞 行每行两个整数 𝑙′, 𝑟′，表示一个询问。

设 𝑙ast 为上次询问的答案，初始为 0。则询问的区间为$[l=l' xor last,r=r' xor last]$，保证$1 \le l \le r \le n$

你需要对该区间回答第 type种询问。

输出格式

对于每一次询问，输出一行一个整数表示答案取模后的结果。

5 3 1
1 2 3 4 5
2 4
3 5
1 3

0
0
1

5 3 2
1 2 3 4 5
2 4
11 13
13 15

8
12
4

5 3 3
1 2 3 4 5
2 4
63 57
169 171

60
168
12

提示与说明