Dot Product

You have two arrays A and B of the same length. You must process three kinds of queries.

• * l r x: add an integer x to all A[i] where l ≤ i ≤ r.

• . l r x: add an integer x to all B[i] where l ≤ i ≤ r.

• ? l r: calculate the sum A[l] · B[l] + ... + A[r] · B[r].

Arrays are 1-indexed. Initially, both arrays are filled with zeroes.

Input

The first line contains two space-separated integers n and m: the arrays' lengths and the number of queries, respectively (1 ≤ n, m ≤ 10^5). The next m lines contain queries in the format described above. In each query 1 ≤ l ≤ r ≤ n and 1 ≤ x < 10^9 + 7.

Output

For each query of the third type, print its result modulo 10^9 + 7 on a separate line.

Examples