13267번 - 쿠키 배열

문제

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

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

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

입력

입력의 첫째 줄에 N 과 K 가 주어진다. (1 ≤ N ≤ 10¹⁸, 0 ≤ K ≤ 1000)

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

출력

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

제한

힌트