There is a chain of length $n$ (an undirected graph where for all $1 \le i < n$, there is an edge between node $i$ and node $i+1$). Each node has an integer weight, where the weight of the $i$-th node is $a_i$. There are $m$ operations, each described as follows:

Operation 1 (Update): Given two nodes $u, v$ on the chain and an integer $d$, add $d$ to the weight of every node on the unique simple path between $u$ and $v$.

Operation 2 (Query): Given two positive integers $l, r$, calculate the sum of the node weight sums of all simple paths on the chain that have a number of nodes between $l$ and $r$ (inclusive). Since the answer can be very large, output the result modulo $1000000007$.

The node weight sum of a simple path with $k$ nodes is the sum of the weights of all $k$ nodes (including the endpoints) on that path. This problem asks for the sum of these weight sums over all simple paths that satisfy the given requirements.

Since the graph is undirected, the paths are also undirected; that is, the path from node $1$ to node $2$ is the same as the path from node $2$ to node $1$. Do not count them twice.

Input

The first line contains two positive integers $n$ and $m$, representing the number of nodes and the number of operations, respectively.

The second line contains $n$ integers, where the $i$-th integer $a_i$ is the initial weight of the $i$-th node.

The next $m$ lines each contain either "1 u v d" or "2 l r" (without quotes), representing an operation 1 (update) or an operation 2 (query), respectively.

Output

For each query, output a single integer on a new line, representing the answer modulo $1000000007$.

Examples

Input 1

5 5
1 1 1 1 1
2 5 5
2 1 2
1 1 2 2
2 1 1
1 1 5 3

Output 1

5
13
9

Note

There is only $1$ simple path with $5$ nodes, and its weight sum is $5$, so the first query outputs $5$.

There are $5$ simple paths with $1$ node, each with a weight sum of $1$; there are $4$ simple paths with $2$ nodes, each with a weight sum of $2$, so the second query outputs $13$.

After adding $2$ to the weights of node $1$ and node $2$, the weight sums of the $5$ simple paths with $1$ node are $3, 3, 1, 1, 1$, so the third query outputs $9$.

Constraints

Let $m'$ be the number of update operations (Operation 1).

For all data, $n \le 200000, m \le 500000, m' \le 100000, 0 \le a_i < 1000000007, 1 \le u \le n, 1 \le v \le n, 0 \le d < 1000000007, 1 \le l \le r \le n$.