구슬 굴리기
면접 대비시간 제한0.5초메모리 제한1024 MB
구슬이 (0,0)에서 시작해 n개의 행을 내려가며 각 행에서 왼쪽이나 오른쪽으로 이동할 때, 주어진 m개의 통로를 모두 지나는 경로의 수를 센다.
문제
아래 그림과 같이 배열된 장애물들 사이로 구슬을 굴린다.
장애물들은 n개의 행에 걸쳐 배치되어 있으며, 구슬은 맨 위의 행부터 맨 아래의 행을 향해 굴러간다. 각 행의 장애물들을 지나면서 구슬은 왼쪽 또는 오른쪽으로 굴러갈 수 있다. 각 행의 번호는 0부터 n-1까지로 주어지며, 그 행의 장애물 사이의 공간은 왼쪽부터 차례로 0으로 주어진다.
(0, 0)의 위치에서부터 아래로 구슬을 굴려갈 때, n-1번 행까지 구슬을 굴리는 경우의 수를 구하는 프로그램을 작성하시오. 단, 구슬은 주어진 m개의 공간을 모두 지나야 한다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 30)이 주어진다. 둘째 줄에는 정수 m(1 ≤ m ≤ 50)이 주어진다. 다음 m개의 줄에는 공간의 위치를 나타내는 행 번호와, 그 행에서의 공간의 번호가 주어진다.
출력
첫째 줄에 답을 출력한다.