407582: GYM102832 J Abstract Painting

Once there was a painter, expert in drawing circles on a canvas. As a tasteful painter, he found that if he drew circles according to the following restrictions, the resulting canvas would look like an abstract painting.

1. The center of any circle must be a grid point on the $$$x$$$-axis.
2. The $$$x$$$-coordinate of any point on any circle must be within the range $$$[0, n]$$$.
3. The radius of any circle must be a positive integer not exceeding $$$5$$$.
4. Any two circles have at most $$$1$$$ intersection point.

Specially, an empty canvas was also considered an abstract painting, as it broke none of the above restrictions.

There had already been $$$k$$$ circles drawn on the canvas, not breaking the above restrictions. The painter could further draw one or more circles on the canvas to get an abstract painting, or he could draw nothing and claim that it was already an excellent abstract painting. He wondered how many different abstract paintings he could possibly get. As the number may be very large, you only need to output it modulo $$$10^9+7$$$.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^3$$$, $$$0 \leq k \leq 5n$$$).

If $$$k > 0$$$, each of the next $$$k$$$ lines contains two integers $$$c$$$ and $$$r$$$ ($$$1 \leq c < n, 1 \leq r \leq \lfloor \frac{n}{2} \rfloor$$$), indicating that there was already a circle centering at $$$(c, 0)$$$ with radius $$$r$$$ on the plane.

It is guaranteed that the drawn $$$k$$$ circles satisfy the above restrictions.

Print the number of different abstract paintings the painter might get, modulo $$$10^9+7$$$.

4 1
1 1

4