U541153 子集位运算

给一个长度为$n$的数组$a_1,a_2,...,a_n$。要求维护两个操作： $1$.修改数组中的一个位置。 $2$.询问区间$[l,r]$所有子集位运算$and$之和，对$10^9+7$取模。 我们定义集合$S=\{l,l+1,...,r\}$，$T$为$S$子集。 $f_T=a_{T_1}\ and\ a_{T_2}\ and...and\ a_{T_k}(k为集合T的大小，若k=0则f_T=0)$ 所有子集位运算$and$之和为$\sum_{\\T\in S}f_T$。

第一行一个正整数$n$。 第二行$n$个数，为数组$a$。 第三行一个正整数$m$。 接下来$m$行格式如下： 修改操作：$1\ x\ y $，将$a_x$修改为$y$。$(1\le x\le n)$ 查询操作：$2\ l\ r$，计算区间$[l,r]$所有子集位运算$and$之和，对$10^9+7$取模。$(1\le l\le r\le n)$

对于每次查询操作输出一行。

对于$30\%$数据，$1\le n,m\le10^3,0\le a_i,y\le10^6$。$\\$ 对于$100\%$数据，$1\le n,m\le10^5,0\le a_i,y\le10^9$。