Wolves 2

Interview

Time limit2sMemory limit512 MB

Summary

Count binary strings of length N in which every given interval contains at most two ones, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Prefix sum, Combinatorics, Implementation
Solved: No attempts yet

Problem

Wolves appear on the road where Yeongseon is standing. The road is divided into $N$ zones, numbered $0$ through $N-1$ . A single zone holds at most one wolf.

Yeongseon knows $M$ pieces of information about the wolves. One piece of information names one interval of zones and means that the interval holds at most two wolves.

Write a program that counts the wolf arrangements satisfying all $M$ pieces of information. An arrangement is decided by whether each zone holds a wolf or not.

Input

The first line contains the number of zones $N$ and the number of pieces of information $M$ . ( $1 \le N, M \le 300$ )

Each of the next $M$ lines contains one piece of information as two integers, the leftmost zone number $L$ and the rightmost zone number $R$ of the interval. ( $0 \le L \le R \le N-1$ ) The interval includes both end zones, and the information means that zones $L$ through $R$ hold at most two wolves in total. The same interval is given more than once in some inputs.

Output

Print the number of possible wolf arrangements modulo 1,000,000,007 on the first line.

Examples3

Example 1
Input
```
5 1
0 4
```
Expected output
```
16
```
Example 2
Input
```
5 2
0 2
1 4
```
Expected output
```
21
```
Example 3
Input
```
10 4
0 3
4 9
2 5
7 9
```
Expected output
```
225
```