KOI 정보학교의 프로그래밍 동아리에는, K군과 O군과 I군의 3명의 부원이 있다.

프로그래밍 동아리에서는 동아리 활동의 스케줄을 짜려고 한다.

내일부터 N일 간의 활동 일정을 결정하려고 한다.

각 활동일의 스케줄은, 각 부원에 대해서는 활동에 참가할지 어떨지의 2 가지가 있고,

부 전체로는 2*2*2=8 가지가 있다.

부실의 열쇠는 단 하나뿐이며, 처음에는 K 군이 가지고 있다.

각 활동일에는, 그 날의 활동에 참가하는 부원 중 어느 1명이 열쇠를 가지고 있어야 하고,

활동 후에 참가한 부원 중 한 명이 열쇠를 가지고 돌아간다.

동아리에서는, 매일 반드시 활동이 행해지도록, 미리 각 활동일의 책임자를 정했다.

책임자는 반드시 그날의 활동에 참석해야 한다.

스케줄을 결정하려고 하는 일수와, 각 활동일의 책임자가 누구인지의 정보가 주어졌을 때,

모든 활동일에 부활동을 실시할 수 있는 스케줄 표의 수를 10007로 나눈 나머지를 찾는 프로그램을 작성하라.

마지막 날은 누구나 열쇠를 가지고 돌아갈 수 있는 것으로 한다.

예로서 [입출력 예 1]을 살펴보자.

2 일간의 스케줄이 주어진다.

1 일째의 책임자는 O 군,

2 일째의 책임자는 I 군이다.

문제문의 조건에 따라 다음 7가지를 생각할 수 있다.

1일차 2일차

(K,O) (O,I)

(K,O) (K,I)

(K,O) (K,O,I)

(K,O,I) (I)

(K,O,I) (K,I)

(K,O,I) (O,I)

(K,O,I) (K,O,I)

각 날짜에 K또는 O또는 I가 참여하는 것을 나타낸다.

1일째 책임자는 O군이지만, 첫 열쇠를 가지고 있는 것은 K군이기 때문에,

첫날 활동에는 K군, O군 모두가 참가할 필요가 있다.

또한 1일째에 열쇠를 가지고 돌아온 사람은 2일째에도 참가해야 하기 때문에

1일째와 2일째 모두에 참가하는 사람이 적어도 1명 존재해야 한다는 점에 주의하여라.

동아리 활동 timer 1초 memory 128MB

동아리 활동 1초 128MB