P. Towers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Arvin is very orz. He is also very rich. He owns the number line, so as to defend it, he has built towers on each integer position of the number line.

Initially, there are $$$n$$$ towers which have a positive number of copies of the magical weapon of bruhopener, in which the $$$i$$$-th tower is at position $$$d_i$$$ and has $$$s_i$$$ bruhopeners. To make the defense stronger, every second, he chooses a tower with at least $$$2$$$ bruhopeners, then moves one of its bruhopeners to the tower on its left and moves the other to the tower on its right. He does this until every tower has at most $$$1$$$ bruhopener.

Arvin can easily figure out how many seconds this process will last for. Therefore, he challenges you to do the same by writing a code. Since the answer might be too large, output the answer modulo $$$10^9+7$$$.

Input

The first line consists of an integer $$$n$$$ ($$$1\le n\le 10^6$$$).

The $$$i$$$-th line of the next $$$n$$$ lines consist of two integers $$$d_i,s_i$$$, the position and number of bruhopeners of the $$$i$$$-th tower which initially has a positive number of bruhopeners ($$$1\le s_i\le 10^6$$$, $$$-10^6\le d_1 \lt d_2 \lt ... \lt d_n\le 10^6$$$).

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$s_i \le 3$$$ and $$$d_i$$$ is a multiple of $$$3$$$.

Tests $$$2-3$$$ satisfy the sum of $$$s_i$$$ does not exceed $$$100$$$.

Tests $$$4-6$$$ satisfy the sum of $$$s_i$$$ does not exceed $$$1000$$$.

Tests $$$7-9$$$ satisfy $$$n=1$$$.

Tests $$$10-11$$$ satisfy $$$n \le 3$$$.

Tests $$$12-16$$$ satisfy $$$n \le 1000$$$.

Tests $$$17-18$$$ satisfy $$$n \le 10^5$$$.

Tests $$$19-20$$$ satisfy no additional constraints.

Output

Output a single integer, the number of seconds that the process will last for, modulo $$$10^9+7$$$.

Example
Input
2
2 3
3 2
Output
8
Note

Due to the large amount of input, Arvin advises you to append the following two lines of code before input:

ios_base::sync_with_stdio(false);

cin.tie(NULL); cout.tie(NULL);

—

Problem Idea: culver0412

Problem Preparation: culver0412

Occurrences: Advanced L