You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

提示与说明