Problem Description

You are given an infinite one-dimensional row of grid cells. At the beginning, every cell is white.

You need to maintain the following two operations:

• 1 l r: Paint every cell from $l$ to $r$ black.

• 2 l r: Query how many sub-intervals in $[l,r]$ have all cells in the interval painted black.

Input Format

The first line contains an integer $n$, which denotes the number of operations.

The next $n$ lines each contain three numbers $opt,l,r$, which denote the operation type and the interval.

Output Format

For each operation of type $2$, output one line containing an integer, which is the answer modulo $\bmod\ 1000000007$.

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

1
10

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\leq n\leq 10^6$, $1\leq opt\leq 2$, $1\leq l\leq r\leq 10^{18}$.

Notes

Translated from AGM 2022 Qualification Round E Intervals。

Translated by ChatGPT 5