409510: GYM103604 E Intervals
Description
Herbert is at school and tries to skip classes. The only problem is that he doesn't want to meet with his teachers when he leaves, so he needs to devise a tactic. Given the intervals of time in seconds when the corridors of the school are free, Herbert can choose any subinterval of those to leave.
Because he likes maths, he challenges himself to count in how many intervals of seconds can he escape the school without being caught. There is a problem: he doesn't have all the free intervals from the beginning of the day. He gets them either via his friends or his own observations. Given the list of free intervals that Herbert discovers, he sometimes stops and thinks in how many ways he could leave if he wanted to go home in a specific interval $$$[L, R]$$$. Help him do this task! He would like this answer to be given modulo $$$1000000007$$$ as he is not good at handling big numbers. Please note that the intervals of time are closed, that means if we have the free intervals $$$[a, b]$$$ and $$$$$$ they can be merged into a bigger interval $$$[a, c]$$$. It can happen the same if the intervals overlap or meet. Further, the intervals are not discovered in chronological order as his friends might not tell him instantly. Also, the length of an interval doesn't really matter, Herbert can move slowly or instantly as he is skilled!
InputThe first line of input contains one integer $$$N$$$($$$1 \leq N \leq 10^6$$$): the total number of free intervals that will be discovered during the day plus the number of questions Herbert will ask.
The next $$$N$$$ lines of input will contain three integers $$$type$$$($$$1 \leq type \leq 2$$$), $$$l$$$ and $$$r$$$($$$1 \leq l \leq r \leq 10^{18}$$$): If $$$type$$$ is $$$1$$$ it means that the interval $$$[l, r]$$$ has been discovered as free. If $$$type$$$ is $$$2$$$ Herbert asks how many subintervals in $$$[l, r]$$$ are free given only the free intervals discovered above it.
OutputFor every query of the second type, print on a line an integer $$$x$$$, denoting the number of free subintervals in the given interval by Herbert modulo $$$1000000007$$$.
ExampleInput4 1 2 2 2 1 5 1 3 5 2 1 5Output
1 10