Rolling a Marble

Interview

Time limit0.5sMemory limit1024 MB

Summary

A marble starts at gap (0,0) and rolls down n rows, moving left or right at each row; count paths that pass through all m required gaps.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

A marble rolls between obstacles arranged as in the figure below.

The obstacles are placed across n rows, and the marble rolls from the top row toward the bottom row. Passing through the obstacles of each row, the marble can roll either left or right. Each row is numbered from 0 to n-1, and the gaps between the obstacles in a row are numbered from 0 starting at the left.

Starting from position (0, 0) and rolling the marble downward, write a program that finds the number of ways to roll the marble to row n-1. The marble must pass through all m given gaps.

Input

The first line gives the integer n (1 ≤ n ≤ 30). The second line gives the integer m (1 ≤ m ≤ 50). The next m lines each give the row number of a gap and the number of that gap within the row.

Output

On the first line, print the answer.

Examples2

Example 1
Input
```
7
2
3 2
5 2
```
Expected output
```
6
```
Example 2
Input
```
30
2
0 0
0 0
```
Expected output
```
536870912
```