COCI 2012/2013 Contest 6- 연속 수열 (JEDAN) > 문제은행 : 정보올림피아드&알고리즘




1690 : 연속 수열 (JEDAN)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
15 회   
시도횟수
66 회   

문제

N개의 음이 아닌 정수들로 이루어진 수열이 있다. 

이런 수열 중 첫 항과 마지막 항은 0이고, 수열의 인접한 두 항의 차이는 항상 0 또는 1인 것을 연속 수열이라고 하자. 

주어진 수열 C에서 몇 개의 부분은 빈칸으로 구성되어 있다. 

 

이 때, 빈칸에 수를 넣어서 연속 수열을 만드는 방법의 수를 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 10,000) 두 번째 줄에는 C1 에서부터 CN 까지 순서대로 주어진다. 단, 각 수는 -1 이상 10,000 이하이며, -1은 빈칸을 의미한다.

출력형식

빈칸에 수를 넣어서 연속 수열을 만드는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

입력 예

3
-1 2 -1

출력 예


입력 예

3
-1 -1 -1

출력 예

2

입력 예

6
-1 -1 -1 2 -1 -1

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP