Problem F
Falling Snow

Picture by dherrera_96

In the cold and remote areas of northern Sweden, a young boy named Anton lives. Being born to a family of pistvakts (an occupation that involves drinking moonshine called “bäverhojt”, hunting bears and occasionally handling safety in the mountains), he has been handed the responsibility of mounting temperature sensors in the Scandinavian Mountains. Anton has to place three identical sensors along the mountain range, which can be modeled as a one-dimensional number line.

A lot of snow fell during the winter, and the sensors need to be placed at points with an ascending order of snow levels, since they work best arranged that way. This means that at the point of the leftmost sensor, the snow level must be strictly less than that of the other sensors, and at the point of the rightmost sensor, the snow level must instead be the strictly higher than that of the other sensors. Anton may also only place sensors at integer points. His house is located at point $0$, and no sensor may be placed to the left of the house.

Even with this limitation, there can be a huge number of ways in which he can place the sensors. Anton has saved the log of where snow has fallen during the winter, given as a number of ranges $[a, b]$, indicating that 1 meter of snow fell between and including points $a$ and $b$. If snow fell $k$ times over a certain point, the snow level in that point is $k$. Can you help him calculate the number of ways he may place the sensors?

Input

The first line of input contains a number $0 \le n \le 10^5$, the number of entries Anton has in his snow log. Then follow $n$ lines, each containing the two numbers $0 \le a \le b \le 10^{18}$, denoting an interval in which snow fell.

Output

Output consists of a single integer – the number of ways in which Anton can place the sensors. This number may be large, so output the remainder modulo $1\, 000\, 000\, 009$. If there is no way Anton can place the sensors, you should instead output the string “shovel time!”, since Anton then must take his snowmobile and manually construct three points with the sought property.

3
1 1
2 3
2 3

2

3
0 0
2 3
2 3

shovel time!