• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

Get your beAr, there is nothing to fear, Colonel’s heavy trace, is again here.

There is an ancient saying that problem I is always one of the hardest problems in programming contests. There is also another not-very-ancient saying that Colonel is still pissed about the fact that the solution to problem F in Tehran Regionals required big integers. Colonel believes the above ancient saying, but what are the probabilities that you’re writing the last problem of the problem set, and there is only one problem slot left, and you contact the contest coordinator to see if they can place your problem on slot I, and they respond with “I is the only remaining slot”?

Lightning strike. Lightning strike indeed. Would’ve been a Full-house if this was a probability problem, but nah we’re not that lucky.

ورودی

In the first line you’ll have $n$ and $m$ .

$$1 \leq n \leq 1000,000, \quad \quad 1 \leq m \leq 1000,000$$ In the next line there will be $n$ numbers forming an array of size $n$.

In each of the next $m$ lines there will a single query of one of the following types: $$1,, a,, b,, k$$

Which updates all the elements in range $a$ to $b$ inclusive, raises each of them individually to the power $k$.

$$42,,a,,b$$

Which asks for the product of all the array elements between $a$ and $b$ inclusive.

خروجی

For each query of type $42$, output a number, the answer to the product of the numbers in the specified range. Since the answer can be very large, print answer modulo $10^9 + 7$.

مثال‌ها

ورودی نمونه ۱

5 5
1 2 3 4 1000
1 2 3 2
1 1 4 4
42 1 1
42 1 2
42 2 5

خروجی نمونه ۱

1
256
981692997