시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 1024 MB188660.000%

문제

아래의 그림과 같이 배열된 장애물들 사이로, 구슬을 굴린다.

장애물들은 n개의 행에 걸쳐 배치되어 있으며, 구슬은 맨 위의 행부터 맨 아래의 행을 향해 구른다. 각 행의 장애물들을 지나면서, 구슬은 왼쪽 또는 오른쪽으로 굴러갈 수 있다. 각 행의 번호는 0부터 n-1까지로 주어지며, 그 행의 장애물 사이의 공간은 왼쪽부터 차례로 0으로 주어진다.

(0, 0)의 위치에서부터 아래로 구슬을 굴려갈 때, n-1번 행까지 구슬을 굴리는 경우의 수를 구하는 프로그램을 작성하시오. 단, 구슬은 주어진 m개의 공간을 모두 지나야 한다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 30)이 주어진다. 둘째 줄에는 정수 m(1 ≤ m ≤ 50)이 주어진다. 다음 m개의 줄에는 공간의 위치를 나타내는 행 번호와, 그 행에서의 공간의 번호가 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

7
2
3 2
5 2

예제 출력 1

6

예제 입력 2

30
2
0 0
0 0

예제 출력 2

536870912