Earn Your Cupcake

mainstring Mirror of NSTU ICE Fest R...
Limits 10s, 1.0 GB

A delicious NxN grid is given to you. All the lattice points of this grid contain a cupcake each except for M specified points. (Those M points do not contain cupcakes.)

Now, you have to randomly choose four different lattice points from this grid. If your four chosen points make a rectangle and each of the four points contains a cupcake, then you will earn a cupcake for yourself.

Calculate the probability of winning a cupcake in the given grid.

Input

First line contains two integers N (1 <= N <= 103) and M (0 <= M <= 50)

Each of next M lines contains two integers Xi(0 <= Xi <= N) and Yi(0 <= Yi <= N) describing the ith point where the cupcake is missing. (each of these points are distinct)

Output

Print one number expressing the probability of earning a cupcake in following format.
If the answer is P/Q, then print the number P ⋅ Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7.

Sample

InputOutput
2 1
1 1
47619048

Submit

Login to submit.

Statistics

100% Solution Ratio
tmwilliamlin168Earliest, Feb '20
tmwilliamlin168Fastest, 0.7s
tmwilliamlin168Lightest, 4.1 MB
Deshi_TouristShortest, 3235B
Toph uses cookies. By continuing you agree to our Cookie Policy.