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 Ai where l ≤ i ≤ r.
• . l r x: add an integer x to all Bi where l ≤ i ≤ r.
• ? l r: calculate the sum Al · Bl + ... + Ar · Br.

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 ≤ 105). The next m lines contain queries in the format described above. In each query 1 ≤ l ≤ r ≤ n and 1 ≤ x < 109 + 7.

Output

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