Chain Path Queries

You are given a chain (an undirected graph) with n nodes, where for all 1 ≤ i < n there is an edge between node i and node i+1. Each node has an integer weight; the weight of the i-th node is a_i.

There are m operations. Each operation is one of the following:

• Operation 1 (Update): Given two nodes u and v and an integer d, add d to every node on the unique simple path between u and v. (Note: if u > v you may assume the path is from v to u.)
• Operation 2 (Query): Given two positive integers l and r, consider all simple paths (which, on a chain, are exactly contiguous segments) that have a number of nodes between l and r (inclusive). The value of a simple path is defined as the sum of the weights of the nodes on that path. Compute the sum over all such simple paths. Since the answer can be large, output it modulo \(1000000007\).

Note: In an undirected graph the simple path from i to j is identical to the path from j to i, so each path should only be counted once.

inputFormat

The first line contains two integers n and m.

The second line contains n integers: a₁ a₂ ... a_n, representing the initial weights of the nodes.

The following m lines each contain an operation. The format of an operation is as follows:

• If the operation begins with 1, it is a modification (update) operation and is followed by three integers u v d.
• If the operation begins with 2, it is a query operation and is followed by two integers l r.

outputFormat

For each query operation (operation type 2), output the corresponding answer modulo \(1000000007\) on a separate line.

sample

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

66
30