Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Earn Your Cupcake

By mainstring · 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

Discussion

Statistics


100% Solution Ratio

tmwilliamlin168Earliest, 7M ago

tmwilliamlin168Fastest, 0.7s

tmwilliamlin168Lightest, 4.1 MB

tmwilliamlin168Shortest, 3384B

Submit

Login to submit