There is an array of $n$ elements, initially filled with ones. You need to write a data structure that processes two types of queries:

• multiply all elements on the segment from $l$ to $r−1$ by number $v$,
• find the sum on the segment from $l$ to $r−1$.

Both operations are performed modulo $10^9+7$.

The first line contains two numbers $n,m\ (1≤n,m≤100,000)$, the size of the array and the number of operations. 

The following lines contain the description of the operations. The description of each operation is as follows:

• 1 l r v: multiply all elements on the segment from $l$ to $r−1$ by number $v\ (0≤l<r≤n,\ 1≤v<10^9+7)$
• 2 l r: find the sum on the segment from $l$ to $r−1\ (0≤l<r≤n)$.