닌자 소녀는 멈추지 않아

미치루

이 저택의 내부는 격자로 구성되어 있는데, 이즈나가 그린 아래 그림과 같이 저택의 위에서부터 $i$번째 행은 $1$열부터 $i-1$번째 열까지 정사각형 격자로, 그리고 $i$번째 열에 직각 이등변삼각형 격자로 구성되어 있어요! 각 격자의 길이는 직각 이등변삼각형의 빗변을 제외하고 모두 $1$입니다!

• 하강(↓): 아래로 한 칸 이동한다. 즉, 만약 현재 위치가 $(x, y)$라면 점 $(x, y - 1)$로 이동한다.
• 회피(→): 오른쪽으로 한 칸 이동한다. 즉, 만약 현재 위치가 $(x, y)$라면 점 $(x + 1, y)$로 이동한다.

그러면… 총 이동 횟수가 $N$인 경로만 고려하겠죠! 또한 저택 밖을 벗어나면 안 되니까 이동 도중에는 항상 변을 포함한 삼각형 내부에 있어야 하고요.

그런데 저택에는 무시무시한 함정들이 있어요! 이즈나가 알아낸 정보에 따르면 이동 중에 다음 조건을 모두 만족해야 한다고 해요!

• $1 \le i \le M$에 대하여, $k_i$번째 이동에서는 이즈나가 있는 위치에 함정이 발동하며, 이 함정에 걸리지 않도록 $c_i$번째 회피(→)를 수행해야 한다.

즉 다시 말해서, $k_i$번째 이동은 반드시 회피(→)여야 하고, 그 회피는 전체 경로에서 반드시 $c_i$번째 회피(→)가 되어야 합니다! 물론, 이즈나는 닌자니까 함정이 없어도 회피(→)할 수 있어요!

저택에는 도착점으로 이어지는 갈림길이 많아, 조건을 만족하는 이동 동선을 모두 아는 것이 중요합니다! 이즈나가 선택 가능한 경로가 몇 개인지 구해보죠! 닌닌!

그 다음 줄부터 $M$번에 걸쳐, 각 줄에 $k_i$, $c_i$가 공백으로 구분되어 주어진다. $(1 \le k_i \le N$; $k_i < k_{i + 1}$; $1 \le c_i \le \frac{N}{2}$; $c_i < c_{i + 1})$

시간 제한

1000 ms

메모리 제한

1024 MB

체커

CUSTOM