|
На шахматной доске размером N×N.
В левой нижней клетке с координатами (1, 1)
стоит шахматный король. Он хочет дойти до правой верхней клетки с координатами
(N, N), при этом ходить он может
только на одну клетку либо вверх либо вправо. Также на доске есть K
запрещенных клеток, в которые король не может заходить. Найдите сколькими
различными способами король сможет совершить свое путешествие, ни разу не зайдя
на запрещенные клетки. Поскольку число способов может быть огромным, то
выведите его по модулю 20 100 703.
Формат входного файла
В первой строке входного файла заданы два целых числа N
и K — размер поля и количество запрещенных клеток, соответственно (2 ≤ N ≤ 1 000 000, 0 ≤ K ≤ 15).
В следующих K строках, через пробел, заданы координаты запрещенных клеток.
Гарантируется, что запрещенные клетки лежат внутри доски и не повторяются.
Также гарантируется, что клетки (1,1) и (N, N)
не являются запрещенными.
Формат выходного файла
В первой строке выходного файла выведите одно число —
количество различных допустимых путей короля по модулю 20 100 703.
Пример
|
Входные данные
|
Выходные данные
|
|
3 1
2 2
|
2
|
|
3 0
|
6
|
|
100
5
2 7
1 3
57 23
89 3
99 4
|
16731189
|
|
