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.


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)


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.


2 1
1 1


Login to submit.


100% Solution Ratio
tmwilliamlin168Earliest, Feb '20
nusuBotFastest, 0.5s
tmwilliamlin168Lightest, 4.1 MB
Kuddus.6068Shortest, 3162B
Toph uses cookies. By continuing you agree to our Cookie Policy.