F. Random Noise
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You're given an array $$$a$$$ of size $$$n$$$ and $$$q$$$ queries.

Each query is one of the following three types:

  1. Set $$$a_i$$$ to value $$$x$$$.

  2. For every $$$l\leq i\leq r$$$, set $$$a_i = a_i\oplus\ 2^{v_i}$$$ where $$$v_i$$$ is a random number between $$$0$$$ and $$$19$$$ (inclusive) chosen on this operation.

  3. Output the expected value of $$$a_i\oplus a_j$$$ for randomly chosen $$$l\leq i\lt j\leq r$$$.

$$$\Large{\oplus}$$$ here denotes the xor operation.

For each type $$$3$$$ query, you should output the answer modulo $$$10^9+7$$$.

Formally, let $$$P=10^9+7$$$. It can be shown that the answer to each query of type $$$3$$$ can be expressed as an irreducible fraction $$$ab$$$, where $$$a$$$ and $$$b$$$ are integers and $$$b\not\equiv0\mod P$$$. For each query, output the integer equal to $$$a\cdot b^{-1}\mod P$$$. In other words, output an integer $$$z$$$ such that $$$0\leq z\lt P$$$ and $$$z\cdot b\equiv a\mod P$$$.

Input

First line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n,q\leq 4\cdot 10^4$$$)

Second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$0\leq a_i\lt 2^{20}$$$)

Next $$$q$$$ lines contain queries.

First integer $$$t$$$ ($$$1\leq t\leq 3$$$) in every query denotes its type.

  • If $$$t = 1$$$, then query record contains two integers $$$i$$$ and $$$x$$$ ($$$1\leq i\leq n,0\leq x\lt 2^{20}$$$);
  • Otherwise it contains two integers $$$l$$$ and $$$r$$$ ($$$1\leq l\leq r\leq n$$$).
Output

For each type $$$3$$$ query, you should output the answer modulo $$$10^9+7$$$ in a new line.

Example
Input
3 9
15 0 7
3 1 3
1 1 0
3 1 3
2 1 1
3 1 3
1 1 0
1 3 0
2 1 3
3 1 3
Output
10
666666676
533368294
625099619