| 파스타 |
|---|
홍길동이 가장 자신 있게 요리할 수 있는 메뉴는 파스타 중에서 ‘토마토 소스’, ‘크림 소스’, ‘해물 소스’ 3종류다. 홍길동은 친구들을 위한 N일 동안의 저녁 식사를 계획하고 있다. 저녁 식사를 최대한 맛있게 준비하기 위해 3종류의 파스타 중 하나를 선택하되 3일 이상 연속하여 동일한 파스타를 만들지는 않을 계획이다. N일 중 K일은 파스타의 종류가 이미 결정되어 있다고 가정할 때 N일 동안 홍길동이 친구들에게 만들어 줄 수 있는 저녁 메뉴의 모든 경우의 수를 구하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
1번째 줄에서는 두 정수 N(3<=N<=100), K(1<=K<=N)가 공백을 사이에 두고 주어진다. 1+i 번째 줄(1<=i<=K)에는 2개의 정수 Ai(1<=Ai<=N), Bi(1<=Bi<=3)가 공백을 사이에 두고 주어진다. Bi는 Ai일에 정해진 파스타의 종류로서 Bi가 1이면 토마토 소스, 2이면 크림 소스, 3이면 해물 소스다. | |
| 출력 | |
|---|---|
1번째 줄에 N일 동안 홍길동이 친구들에게 만들어 줄 수 있는 저녁 메뉴의 모든 경우의 수를 10000으로 나눈 나머지를 출력한다. 예시1의 경우, 5일 동안 저녁 식사를 계획하고 있으며 1일째와 3일째는 토마토 소스, 4일째는 크림 소스가 결정되어 있다. 3일 이상 연속해서 동일한 종류의 파스타를 만들지 않는 조건 하에 가능한 메뉴의 조합은 다음의 6가지다.
예시2의 경우, 조건에 맞은 경우의 수는 4112640이므로 10000으로 나눈 나머지는 2640이다 | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 5 3 3 1 1 1 4 2 | |
| 출력 | 6 | ||
| 2 | 입력 | 20 5 10 2 4 3 12 1 13 2 9 1 | |
| 출력 | 2640 | ||