23317번 - 구슬 굴리기

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

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

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

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

첫째 줄에 답을 출력한다.