Painting the Balls

Time limit2sMemory limit512 MB

Summary

Given M range-painting operations used in order with unknown colors, count how many distinct final black/white ball colorings are possible.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics
Solved: No attempts yet

Problem

$N$ balls sit in a row. A ball can be painted black or white, and every ball is white at the start. The leftmost ball is ball 1, and the balls are numbered in order from left to right.

Today you want to paint the balls. A machine does the painting, and it reads two integers $L$ and $R$ . The machine paints ball $L$ through ball $R$ entirely in one color, either white or black.

You used the machine $M$ times in total, and you know every $L$ and $R$ you gave it. You forgot which color each use painted.

Write a program that counts how many color combinations can appear after all $M$ uses of the machine.

Input

The first line contains the number of balls $N$ and the number of machine uses $M$ . ( $1 \le N \le 1000$ , $1 \le M \le 50$ )

Each of the next $M$ lines contains the $L$ and $R$ given to the machine, in the order the machine was used. ( $1 \le L \le R \le N$ )

Output

Print the number of color combinations that can appear. The answer is at most $2^{63}-1$ .

Examples3

Example 1
Input
```
4 3
1 1
2 2
3 3
```
Expected output
```
8
```
Example 2
Input
```
3 3
1 3
1 1
2 3
```
Expected output
```
4
```
Example 3
Input
```
1000 1
47 747
```
Expected output
```
2
```