409821: GYM103797 H High Profile Math

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. High Profile Mathtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Andrade and his followers… love to skip their programming classes… to study High Profile Math (HPM)… (it was supposed to be Low Profile Math… but the professor is so good… that his subject got an upgrade… Hmmm…)

They were watching the recorded classes on HPM together when they noticed a pattern: the professor always talks about exactly $$$N$$$ topics and in the middle of each topic he takes a long pause to… apparently do nothing. They were getting bored of studying, so they decided to play a game! Each of Andrade's followers will guess how long one of the $$$N$$$ pauses of their next HPM class will last. Then, Andrade, infamous icoschampion (20 times champion) of the iberoamerican math olympics, has to calculate the expected value for the total pause time of the next class, considering that each pause could last each guessed amount with equal probability. They want to see how close their guesses were.

But Andrade found the task too easy (of course), so, in the HPM spirit, he took his result as an irreducible fraction $$$\frac{p}{q}$$$ and changed it to $$$p * q^{-1} \pmod{10^9+7}$$$, where $$$q^{-1}$$$ is such that $$$q * q^{-1} \equiv 1 \pmod{10^9+7}$$$.

As no one is able to keep up with Andrade, your task is to make a program that checks if Andrade got the right result, even though you know he did. You need to make a fast program, since HPM has lots of topics and Andrade has lots of followers!

Input

The first line contains a single integer $$$N$$$ ($$$0 < N \leq 10^5$$$) — the number of topics.

The second line contains a single integer $$$M$$$ ($$$N \leq M \leq 10^5$$$) — the number of Andrade's followers.

The next $$$M$$$ lines contain two integers each, $$$a_i$$$ ($$$0 < a_i \leq N$$$) and $$$b_i$$$ ($$$0 \leq b_i \leq 100$$$) — the topic Andrade's $$$i$$$-th follower wants to guess about and the amount of time he guesses, respectively.

There will always be at least one guess for each topic.

Output

A single line consisting of the expected value in the way described.

ExamplesInput
3
3
1 0
2 100
3 5
Output
105
Input
1
2
1 5
1 10
Output
500000011

加入题单

上一题 下一题 算法标签: