시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 73 | 13 | 11 | 23.913% |
언제나 그랬듯이, 데브베이커리에서는 쿠키를 굽고 있다! 오늘 데브베이커리에서 굽는 쿠키는 딱 2 가지로, 2×1 크기의 ‘명랑한 쿠키양’과 1×1 크기의 ‘용감한 쿠키군의 머리’쿠키이다.
데브베이커리에서는 쿠키들을 구울 때, 쿠키들을 정확히 N×5 모양으로 배치하여 굽는다. 1×1 크기의 쿠키는 정확히 K 개 굽는데, 쿠키들을 배치할 때, 먼저 1×1 크기의 쿠키들을 모두 배치한 후에 그 다음으로 2×1 크기의 쿠키를 채워 넣어서 빈 칸이 없도록 쿠키를 굽는다. (쿠키를 돌려서 배치할 수도 있다)
N 과 K, 그리고 1×1 크기의 쿠키의 배치 위치가 주어졌을 때, 2×1 크기의 쿠키를 배치하는 경우의 수를 구하여라.
입력의 첫째 줄에 N 과 K 가 주어진다. (1 ≤ N ≤ 1018, 0 ≤ K ≤ 1000)
둘째 줄부터 K+1 번째 줄에 쿠키의 위치를 나타내는 좌표가 두 개의 정수로 주어진다.
2×1 크기의 쿠키를 배치하는 경우의 수를 1,000,000,007 로 나눈 나머지를 출력한다.
2 2 1 1 2 1
5
University > KAIST > 2016 KAIST 6th ACM-ICPC Mock Competition C번