考虑维护一个这样的问题： （1） 给出一个数组A，标号为1~n （2） 修改数组中的一个位置。 （3） 询问区间[l,r]中所有子集的位运算and之和mod(109+7)。 位运算and即为“pascal中的and”和“CC++中的&” 我们定义集合S={ l , l+1 , ... , r-1 , r} 若集合T，T ∩ S = T，则称T为S的子集 设f（T）=AT1 and AT2 and ... and ATk (设k为T集大小，若k=0则f(T)=0) 所有子集的位运算and之和即为∑f(T) 那么，现在问题来了。
输入描述:
第一行，一个正整数N第二行，N个非负整数，为数组A第三行，一个正整数M，为操作次数接下来M行格式如下修改操作： 1 x y，将Ax修改为y询问操作： 2 l r，区间[l,r]中所有子集的位运算and之和 mod(109+7)


输出描述:
对于每次询问输出一行，为该次询问的答案mod(109+7)。long long 请使用lld
示例1

输入

3
1 2 3
6
2 1 3
1 1 2
2 1 3
2 2 3
1 2 5
2 1 3

输出

9
15
7
13

说明

第一次询问：
Answer =1+2+3+(1 and 2)+(1 and 3)+(2 and 3)+(1 and 2 and 3)
=1+2+3+0+1+2+0
=9
第二次询问：
Answer =2+2+3+(2 and 2)+(2 and 3)+(2 and 3)+(2 and 2 and 3)
=2+2+3+2+2+2+2
=15
第三次询问：
Answer =2+3+(2 and 3)
=2+3+2
=7
第四次询问：
Answer =2+5+3+(2 and 5)+(2 and 3)+(3 and 5)+(2 and 5 and 3)
=2+5+3+0+2+1+0
=13

备注:
M,N≤105,Ai≤109
加载中...