시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 58 8 7 17.949%

문제

언제나 그랬듯이, 데브베이커리에서는 쿠키를 굽고 있다! 오늘 데브베이커리에서 굽는 쿠키는 딱 2 가지로, 2*1 크기의 ‘명랑한 쿠키양’과 1*1 크기의 ‘용감한 쿠키군의 머리’쿠키이다.

데브베이커리에서는 쿠키들을 구울 때, 쿠키들을 정확히 N * 5 모양으로 배치하여 굽는다. 1 * 1 크기의 쿠키는 정확히 K 개 굽는데, 쿠키들을 배치할 때, 먼저 1 * 1 크기의 쿠키들을 모두 배치한 후에 그 다음으로 2 * 1 크기의 쿠키를 채워 넣어서 빈 칸이 없도록 쿠키를 굽는다. (쿠키를 돌려서 배치할 수도 있다)

N 과 K, 그리고 1*1 크기의 쿠키의 배치 위치가 주어졌을 때, 2 * 1 크기의 쿠키를 배치하는 경우의 수를 구하여라.

입력

입력의 첫째 줄에 N 과 K 가 주어진다. (N <= 10^18, K <= 1000)

둘째 줄부터 K+1 번째 줄에 쿠키의 위치를 나타내는 좌표가 두 개의 수로 주어진다.

출력

2 * 1 크기의 쿠키를 배치하는 경우의 수를 1,000,000,007 로 나눈 나머지를 출력한다.

예제 입력

2 2
1 1
2 1

예제 출력

5

힌트