# Practice on Toph

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

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

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 <= 10^{3}) and M (0 <= M <= 50)

Each of next M lines contains two integers X_{i}(0 <= X_{i} <= N) and Y_{i}(0 <= Y_{i} <= 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 10^{9}+7**, where Q

Input | Output |
---|---|

2 1 1 1 | 47619048 |

100% Solution Ratio

tmwilliamlin168Earliest,

tmwilliamlin168Fastest, 0.7s

tmwilliamlin168Lightest, 4.1 MB

tmwilliamlin168Shortest, 3384B

Login to submit