시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 26 17 10 52.632%

문제

영선이는 길 위에 혼자 서있다. 영선이가 서있는 길에는 늑대가 나타나기 때문에 매우 조심스러워 졌다.

도로는 N개의 구역으로 나누어져 있고, 구역은 0번부터 N-1번까지 번호가 매겨져 있다. 각 구역에는 최대 1마리의 늑대가 존재한다.

영선이는 늑대가 나타나는 정보를 총 M개 가지고 있다. 각각의 정보는 구간으로 이루어져 있으며, 그 구간에 늑대가 최대 두 마리 존재한다는 것이다.

늑대가 최대 두 마리 존재하는 구간에 대한 정보를 M개 가지고 있을 때, 도로에 있을 수 있는 늑대 배치의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 구간의 개수 N과 정보의 수 M이 주어진다. (1 ≤ N, M ≤ 300)

둘째 줄부터 M개의 줄에는 늑대가 최대 두 마리 존재하는 구간에 대한 정보의 왼쪽 끝 구역 L과 오른쪽 끝 구역 R이 주어진다. 구간은 양 끝 구역을 포함한다.

출력

첫째 줄에 늑대가 있을 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

5 1
0 4

예제 출력 1

16

예제 입력 2

5 2
0 2
1 4

예제 출력 2

21

예제 입력 3

10 4
0 3
4 9
2 5
7 9

예제 출력 3

225