hewmatt10 has been banished to the Ministry of [REDACTED]! Knowing that this may very well be the end of Art Academy, once and for all, he wants to rebel as much as possible during his final moments, and decides to show off what [REDACTED] despises the most: the art of math.

He begins by creating an array of ~N~ elements, indexed from ~1~ to ~N~, initialized with the elements ~a_1, a_2, a_3 ... a_N~. There are ~Q~ queries that will need to be performed on this array.

The queries will be in the following format:

Format Description	Query Description
~1~ ~l~ ~r~ ~e~ ~c_0~ ~c_1~ ~c_2~ ~...~ ~c_e~	Let us define a polynomial function ~f(x) = c_0 + c_1x + c_2x^2 ... + c_ex^e~. For each element ~a_i~ between ~l~ and ~r~ inclusive, increment ~a_i~ by ~f(i)~.
~2~ ~l~ ~r~	Calculate the sum of all the elements from ~l~ to ~r~ inclusive, modulo ~10^9 + 7~. Ensure that the result of the modulo is always positive.

Unfortunately, even hewmatt10 forgets how to perform such difficult queries sometimes, so he is asking you for your help! Can you help hewmatt10 perform queries on an array?

Input Specification

On the first line, there will be two space-separated integers, ~N~ ~(1 \le N \le 5 \times 10^5)~ and ~Q~ ~(1 \le Q \le 5 \times 10^4)~.

On the second line, there will be ~N~ space-separated integers, ~a_0, a_1, a_2 ... a_N~, the initial values of the array. ~(0 \le |a_i| \le 10^6)~. ~|a_i|~ denotes the absolute value symbol.

The next ~Q~ lines contain a query in the format specified above, where ~1 \le l \le r \le N~, ~0 \le e \le 10~, and ~(0 \le |c_i| \le 10^6)~. Note that for query ~1~, there will always be ~e + 1~ integers following the integer ~e~.

Output Specification

For each type ~2~ query, output a single integer representing the result of the calculation on a newline.

Subtasks

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

Subtask	Points	Description
1	15	~1 \le N, Q \le 10^2~. There will be no queries of type ~1~.
2	35	For all type ~1~ queries, ~e \le 1~.
3	50	No further constraints.

Sample Input 1

5 3
7 6 5 4 3
1 1 4 2 0 0 1
2 4 5
2 1 4

Sample Output 1

23 
52

Explanation

In the first query, the function ~f(x)~ is ~0 + 0x + 1x^2~, which is simply ~x^2~. The elements from index ~1~ to ~4~ are incremented by ~f(1)~, ~f(2)~, ~f(3)~, and ~f(4)~ respectively, meaning that the new array is 8 10 14 20 3.

The sum of the elements from index ~4~ to ~5~ is ~20 + 3~.

The sum of the elements from index ~1~ to ~4~ is ~8 + 10 + 14 + 20~.

Sample Input 2

10 3
-5 -4 -3 -2 -1 0 1 2 3 4
1 2 10 10 -1 1 -1 1 -1 1 -1 1 -1 1 -1
2 1 10
2 1 1

Sample Output 2

508532018
1000000002