According to unreliable rumors, Lu Bu was actually a studious child. His later transition from literature to martial arts stemmed from a number-guessing game his father once played with him.

His father would secretly write an integer on a piece of paper and tell Lu Bu that the number was between $1$ and $K$. Then, Lu Bu would make $N$ consecutive guesses. Each time, he would guess two numbers $X_1, X_2$ (guaranteed to have different parity). His father would then tell him which of the two numbers was closer to the number on the paper.

For example, if the number on the paper is $8$ and Lu Bu guesses $4$ and $11$, his father would tell him that $11$ is closer (because the distance between $11$ and $8$ is $3$, while the distance between $4$ and $8$ is $4$).

Now, it is known that Lu Bu made $N$ guesses, and the results of these $N$ guesses are sufficient for a normal person to deduce what the number is. However, Lu Bu failed to figure it out. His father was very angry, gave you the $N$ guesses Lu Bu made, and did not tell you the result of each guess (meaning you cannot obtain the feedback from his father).

Question: How many possible sequences of feedback could the father have given? For simplicity, you only need to output a single number representing the number of possibilities. See the examples for more details.

Input

The first line contains an integer $K$, representing the range of the number on the paper. The second line contains an integer $N$, representing the number of times Lu Bu guessed. The next $N$ lines each contain two integers $X_1, X_2$, representing the two numbers Lu Bu guessed in that turn.

Output

A single integer representing the number of possible answers.

Examples

Input 1

4
3
1 4
1 2
2 3

Output 1

2

Note

Suppose the answer is $1$, then the father's feedback is $(1, 1, 2)$. Clearly, based on the first two queries, it is already possible to conclude the answer is $1$.

Suppose the answer is $2$, then the father's feedback is $(1, 2, 2)$. Clearly, based on the first two queries, it is already possible to conclude the answer is $2$.

Suppose the answer is $3$ or $4$, then the father's feedback is $(4, 2, 3)$ in both cases. Thus, we clearly cannot determine whether the answer is $3$ or $4$.

Therefore, there are only two possible sequences of feedback from the father: $(1, 1, 2)$ or $(1, 2, 2)$.

Constraints