근시

2019 ICPC Asia Jakarta Regional Contest를 준비하던 Budi는 자료 구조 문제를 하나 발견했다. 그런데 문제를 잘못 읽었고, 자기가 생각한 문제가 원래 문제보다 훨씬 재미있다고 주장하며 이 문제를 만들었다.

정수 배열 $A_{1..N}$에 대한 함수 $f(L, R)$을, 모든 $L \le i \le j \le R$에 대해 부분 배열 $A_{i..j}$의 각 원소를 1씩 증가시키는 연산으로 정의하자. 다시 말해 함수 $f(L, R)$은 다음과 같다(의사 코드).

function f(L, R):
  FOR i from L to R
    FOR j from i to R
      FOR k from i to j
        Ak = Ak + 1

$N$개의 원소로 이루어진 배열 $A$가 주어진다(처음에는 모든 $i = 1..N$에 대해 $A_i = 0$). $A$에 다음 두 종류의 질의를 $Q$번 수행하라.

• 1 L R — $A$에 $f(L, R)$을 수행한다.
• 2 L R — $L \le i \le R$인 모든 $A_i$의 합을 출력한다.

첫 줄에 두 정수 $N$, $Q$가 주어진다($1 \le N, Q \le 100\,000$). $N$은 $A$의 크기이고 $Q$는 질의의 수이다. 다음 $Q$개의 줄에 각각 다음 형태의 질의가 주어진다.

• 1 L R ($1 \le L \le R \le N$)
• 2 L R ($1 \le L \le R \le N$)

두 번째 종류의 질의가 적어도 하나 있다.

두 번째 종류의 질의마다, 입력에 주어진 순서대로 $L \le i \le R$인 모든 $A_i$의 합을 한 줄에 출력한다. 값이 클 수 있으므로 출력을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.