闽西阔少张某在实行海王计划后，果然大有收获，心想我张家必将晋升世家，但是他发现，单靠他一人了解这些妹妹时间远远不够，于是他花了一 亿 美 金，去青青草原请喜羊羊公子(划掉，去京城请带数据分析师许某掌管大局，经过许某的分析，给这n个妹妹设定了n个魅力值ai，但是许某发现单一的魅力值有误差，并且魅力值会有浮动的现象,只有某个区间的所有子集与之和才能作为判断依据。(不理解的话看下样例解释就懂了)
所以张某请来了Rook1e帮他写个程序分析一下，但是Rook1e不会，于是把这个问题扔给你这个天才acmer了。
良心出题人：
子集的含义为 对于一个集合A 如果存在集合B 满足 B∩A = B 则称B是A的子集
题面中的 与 代表C/C++位运算中的 &
单组数据
第一行，一个整数n 代表妹子个数 1 <= n <= 1e5
第二行，n个非负整数ai，第i个ai值代表第i个妹子的魅力值
第三行，一个整数q代表查询次数 1 <= q <= 1e5
接下来的q行格式为：
每一行先输入一个整数op代表操作种类
op = 1 输入 x,y 两个整数 将a[x]的值修改成y x为下标 1<= x <=n
op = 2 输入 l,r 两个整数 输出区间 [l,r] (闭区间) 中所有子集的与之和 ，由于输出可能过大，对答案取模1e9 + 7
ai和y均小于1e8
对于询问op = 2输出一行，代表答案
3 1 2 3 5 2 1 3 1 2 7 2 1 3 1 1 2 2 1 3
9 17 21 hint:1 + 2 + 3 + (1 & 2) + (1 & 3) + (2 & 3) + (1 & 2 & 3) = 9