공 색칠하기

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

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

기계를 모두 $M$번 사용했고, 그때 입력한 $L$과 $R$은 전부 알고 있다. 하지만 어떤 색으로 칠했는지는 잊어버렸다.

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

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

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

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