A. Card Dealer Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two players are competing in a two-player game involving $$$n$$$ decks of cards. The $$$i$$$-th deck contains $$$p_i$$$ red cards and $$$q_i$$$ blue cards. The cards in each deck are indistinguishable from one another when placed face down.

The game consists of $$$n$$$ rounds, with each round played as follows:

  1. At the beginning of each round, one player is assigned the role of the dealer and the other the role of the guesser.
  2. The dealer chooses one of the remaining decks and shuffles the cards, placing them face down on the table.
  3. The guesser selects one card from the deck and flips it over:
    • If the card is red, the roles remain the same for the next round.
    • If the card is blue, the roles are switched for the next round, with the dealer becoming the guesser and the guesser becoming the dealer.
  4. Once a deck is used in a round, it is discarded and cannot be chosen again.
The game continues for $$$n$$$ rounds, with all decks being used exactly once. The player who is the dealer at the end of the $$$n$$$-th round is declared the winner.

Given that both players are playing optimally and know the exact composition of each deck (i.e., the number of red and blue cards in each deck), determine the probability that the player who starts as the dealer will win the game.

Let $$$P = 1\,000\,000\,007$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod P$$$. Output the integer equal to $$$x\cdot y^{-1} \pmod P$$$. In other words, output such an integer $$$a$$$ that $$$0 \le a \lt P$$$ and $$$a\cdot y=x \pmod P$$$.

Input

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the number of decks. The $$$i$$$-th of the following $$$n$$$ lines contains two integers $$$p_i$$$ and $$$q_i$$$ ($$$0 \le p_i, q_i \le 10^6$$$, $$$p_i + q_i \gt 0$$$): the number of red cards and the number of blue cards in the $$$i$$$-th deck, respectively.

Output

Print the answer modulo $$$1\,000\,000\,007$$$ in a single line.

Examples
Input
1
1 2
Output
333333336
Input
4
2 3
3 5
4 7
1 4
Output
96818183
Note

In the first example, the dealer has $$$\frac{1}{3}$$$ chance of winning if the guesser flips up a red card.