문제
진흥이는 학교의 임원으로 환경개선을 위해 학교 담장을 여러 가지 색깔로 예쁘게 색칠하는 중이다.
지금 색칠하는 부분을 N개의 구역으로 나누어서 여러 가지 색깔로 각각의 위치를 칠하려고 한다.
이미 다른 색이 일부 칠해져 있고 이번에는 노란색을 칠할 차례이다.
노란색은 어떤 곳이든 여러 곳에 칠할 수 있지만 어떤 한 곳에 칠해지면 그 이웃에 위치한 곳은 같은 색을 칠해서는 안된다.
물론 노란색을 아예 칠하지 않을 수도 있다.
진흥이는 문득 현재 상태에서 노란색을 칠할 수 있는 방법이 몇가지나 있을지 궁금해졌다.
처음부터 한가지씩 세어보다가 너무 많아서 그냥은 셀 수 없다는 것을 알게 되었다.
진흥이를 위해 노란색을 칠할 수 있는 방법이 몇 가지나 있을지 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에는 색칠을 해야하는 담장의 크기 N이 입력된다. (1 <= N <= 1000)
다음 줄에는 N개의 한 자리 정수가 입력되는데 담장의 칠해진 상태를 나타낸다.
0은 아직 칠해지지 않은 부분이고 다른 수들은 지금까지 칠해진 색을 의미한다.
출력
노란색을 칠할 수 있는 방법이 몇 가지인지 경우의 수를 구하여 10007로 나눈 나머지를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N = 5 |
| #2 | 20점 | 현재까지 칠해진 색깔은 없다. 즉 색깔을 나타내는 모든 수는 0이다. |
| #3 | 70점 | 추가적인 제약 조건이 없다. |
예제
5
1 0 0 0 0
8
힌트
로그인해야 코드를 작성할 수 있어요.