29318번 - Съёмка 다국어

До финального матча чемпионата Берляндии остались считанные дни! Но, так как всё делается в последний момент, некоторые организационные моменты ещё не улажены. В том числе нужно организовать съёмку матча. В городе есть несколько компаний, которые готовы организовать съёмку. Но они все конкурируют, и хотят снимать матч, а не операторов конкурентных компаний!

Операторов можно разместить на трибунах стадиона. Трибуны состоят из $n$ рядов: в первом $2n-1$ место, во втором --- $2n-3$, $\ldots$, в $n$-м --- одно. Однако, не все подходят к матчу безответственно, и некоторые болельшики уже купили себе билеты на определённые места. Соответственно, операторов можно поставить только на свободные.

Пример стадиона. Серым отмечены места, которые снимаются операторами. Чёрным --- занятые зрителями места. Операторы отмечены крестиками. Для каждого из них показано, что снимает его камера.

Но конкуренция есть не везде, и все операторы используют камеры одной и той же модели, неизменяемый угол обзора которой позволяет снимать три места в следующем ряду, пять --- через ряд, итд. Власти хотят, чтобы всё прошло на высшем уровне, и попросили предоставить им возможные способы расставить операторов, чтобы самим выбрать наиболее оптимальный. Однако, начальство стадиона не считает это хорошей идеей, полагая, что таких способов очень много. Помогите им выяснить, сколько же существует способов.

В первой строке заданы числа $n$ и $m$ ($1 \le n \le 2000$, $0 \le m \le 1000$) --- число рядов и количество занятых мест.

Далее в $m$ строках заданы занятые места по одному в строке. Место задается двумя числами: $r$ и $p$ ($1 \le r \le n$, $1 \le p \le 2(n-r) + 1$) --- номер ряда и номер места в этом ряду.

Выведите остаток от деления количества способов на $10^9+7$.