Anwar has an array $$$A$$$ consisting of $$$N$$$ integers on which he performs $$$M$$$ operations.

In the $$$j_{th}$$$ operation he will perform one of the following tasks:

• If T$$$_{j}$$$=1, then add $$$F(A_{i})$$$ to $$$A_{i}$$$ for each $$$i$$$ in the interval $$$[L_{j},R_{j}]$$$, where $$$(1 \leq L_{j} \leq R_{j} \leq N)$$$
• If T$$$_{j}$$$=2, then do all operations of the first type from the $$$L_{j}$$$ operation to the $$$R_{j}$$$ operation again in the same order, where $$$(1 \leq L_{j} \leq R_{j} \leq N)$$$.

$$$F(x)$$$ is defined as the largest power of 2 that divides x. For example, $$$F(4)=4, F(5)=1$$$.

Find the final values in $$$A$$$ after performing all operations. Since the answer may be very large return the elements of $$$A$$$ modulo $$$10^9+7$$$.