시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 73 30 29 49.153%

문제

공 N개가 한 줄로 놓여져 있다. 공은 검정색 또는 흰색으로 칠할 수 있으며, 처음에 모든 공의 색은 흰색이다. 공은 가장 왼쪽이 1번이고, 순서대로 번호가 매겨져 있다.

오늘은 공을 칠해보려고 한다. 공은 기계를 이용해서 칠할 수 있는데, 기계는 두 정수 L과 R을 입력으로 받는다. 기계는 L번째 공부터 R번째 공까지를 흰색이나 검정색으로 모두 칠한다.

기계를 총 M번 사용했고, 이때 입력한 L과 R을 모두 알고있다. 하지만, 어떤 색으로 칠했는지는 까먹고 말았다. 

기계를 모두 M번 사용했을 때, 나올 수 있는 색 조합의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공의 개수 N과 기계를 사용한 횟수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 50)

둘째 줄부터 M개의 줄에는 기계를 사용할 때 입력한 L과 R이 기계를 사용한 순서대로 주어진다. (1 ≤ L ≤ R ≤ N)

출력

첫째 줄에 나올 수 있는 색 조합의 수를 출력한다. 정답은 263-1보다 작거나 같다.

예제 입력 1

4 3
1 1
2 2
3 3

예제 출력 1

8

예제 입력 2

3 3
1 3
1 1
2 3

예제 출력 2

4

예제 입력 3

1000 1
47 747

예제 출력 3

2