시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB273285057428.830%

문제

상근이는 성적 향상을 기원하며 N열짜리 제단을 만들기로 했다.

제단의 각 열의 높이는 모두 정수이며, 가장 처음에 모든 열의 높이는 0이다. 제단은 다음과 같은 과정을 통해서 만들어진다. 먼저, 같은 높이를 가지는 연속하는 열을 선택한다. 그 다음, 선택한 첫 열과 마지막 열을 제외한 모든 열의 높이를 1만큼 올린다.

아래 그림은 제단을 쌓는 과정의 예시이다.

수백년이 흐르는 동안 많은 도둑들이 제단의 일부 열을 훔쳐갔다. 상근이의 손자의 손녀의 손자의.... 손녀는 남은 제단의 높이를 가지고, 가능한 제단의 경우의 수를 세려고 한다.

제단의 높이가 주어졌을 때, 남아있는 제단의 높이와 일치하는 제단의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 제단의 열의 수 N이 주어진다. (1 ≤ N ≤ 10,000)

다음 줄에는 공백으로 구분된 N개의 정수 hi가 주어진다. (-1 ≤ hi ≤ 10,000) hi는 i번 열의 높이를 나타내며, -1인 경우에는 도둑이 그 열을 훔쳐간 상태를 나타낸다.

출력

첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
-1 2 -1

예제 출력 1

0

예제 입력 2

3
-1 -1 -1

예제 출력 2

2

예제 입력 3

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

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjU2MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MWNcdWIyZTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMxMzFcdWM4MDEgXHVkNWE1XHVjMGMxXHVjNzQ0IFx1YWUzMFx1YzZkMFx1ZDU1OFx1YmE3MCBOXHVjNWY0XHVjOWRjXHViOWFjIFx1YzgxY1x1YjJlOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MWNcdWIyZThcdWM3NTggXHVhYzAxIFx1YzVmNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgXHViYWE4XHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJhYThcdWI0ZTAgXHVjNWY0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCAwXHVjNzc0XHViMmU0LiBcdWM4MWNcdWIyZThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNFx1YjJlNC4gXHViYTNjXHVjODAwLCBcdWFjMTlcdWM3NDAgXHViMTkyXHVjNzc0XHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWIyOTQgXHVjNWY0XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVjMTIwXHVkMGRkXHVkNTVjIFx1Y2NhYiBcdWM1ZjRcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzVmNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgMVx1YjljY1x1ZDA3YyBcdWM2MmNcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjODFjXHViMmU4XHVjNzQ0IFx1YzMxM1x1YjI5NCBcdWFjZmNcdWM4MTVcdWM3NTggXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzI0MDViNzFkLWY2OTEtNGM4Yi04ZTRjLWNlOWRlZGFiZDg1YVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTc0cHg7IGhlaWdodDogOTNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHViYzMxXHViMTQ0XHVjNzc0IFx1ZDc1MFx1Yjk3NFx1YjI5NCBcdWIzZDlcdWM1NDggXHViOWNlXHVjNzQwIFx1YjNjNFx1YjQ1MVx1YjRlNFx1Yzc3NCBcdWM4MWNcdWIyZThcdWM3NTggXHVjNzdjXHViZDgwIFx1YzVmNFx1Yzc0NCBcdWQ2ZDRcdWNjZDBcdWFjMTRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWMxOTBcdWM3OTBcdWM3NTggXHVjMTkwXHViMTQwXHVjNzU4IFx1YzE5MFx1Yzc5MFx1Yzc1OC4uLi4gXHVjMTkwXHViMTQwXHViMjk0IFx1YjBhOFx1Yzc0MCBcdWM4MWNcdWIyZThcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzgxY1x1YjJlOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YzEzOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxY1x1YjJlOFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YzgxY1x1YjJlOFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM2NDAgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YzgxY1x1YjJlOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxY1x1YjJlOFx1Yzc1OCBcdWM1ZjRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBoPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMSAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMTAsMDAwKSBoPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4IFx1YzVmNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCAtMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViM2M0XHViNDUxXHVjNzc0IFx1YWRmOCBcdWM1ZjRcdWM3NDQgXHVkNmQ0XHVjY2QwXHVhYzA0IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjODFjXHViMmU4XHVjNzU4IFx1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjU2MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKRURBTiIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSBwZW9wbGUgbGlrZSB0byBwcmV0ZW5kIHRoYXQgdGhleSBhcmUgYSBwaGFyYW9oLiBPciBhIGRvbHBoaW4uIEx1a2EgaXMgb25lIHN1Y2ggcGVyc29uLjxcL3A+XHJcblxyXG48cD5IZSBoYXMgYnVpbHQgYSByZWxpZWYgY29uc2lzdGluZyBvZiBhIGxvbmcgbGluZSBvZiBOIGNvbHVtbnMgd2l0aCBub25uZWdhdGl2ZSBpbnRlZ2VyIGhlaWdodHMuIFRoZSBoZWlnaHRzIG9mIGFsbCBjb2x1bW5zIHdlcmUgaW5pdGlhbGx5IHplcm8uIFRoZSByZWxpZWYgd2FzIGJ1aWxkIGluIHN0ZXBzLCB3aGVyZSBpbiBlYWNoIHN0ZXAgTHVrYSB3b3VsZCBzZWxlY3QgYSBjb250aWd1b3VzIHN1YnNlcXVlbmNlIG9mIGNvbHVtbnMgd2l0aCBlcXVhbCBoZWlnaHRzIGFuZCByYWlzZSBhbGwgY29sdW1ucyBpbiB0aGUgc3Vic2VxdWVuY2UsIGV4Y2VwdCB0aGUgZmlyc3QgYW5kIGxhc3QgY29sdW1uLCBieSBvbmUuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMjQwNWI3MWQtZjY5MS00YzhiLThlNGMtY2U5ZGVkYWJkODVhXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NzRweDsgaGVpZ2h0OiA5M3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5IdW5kcmVkcyBvZiB5ZWFycyBoYXZlIHBhc3NlZCwgYW5kIHNvbWUgb2YgdGhlIGNvbHVtbnMgaGF2ZSBiZWVuIHN0b2xlbi4gTHVrYSYjMzk7cyBncmVhdC1ncmVhdC0uLi4tZ3JlYXQtZ3JhbmRzb24gaXMgdHJ5aW5nIHRvIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHJlbGllZnMgdGhhdCBjb3VsZCBoYXZlIGJlZW4gYnVpbHQgYnkgTHVrYSBzdWNoIHRoYXQgdGhlIHJlbWFpbmluZyBjb2x1bW5zJiMzOTsgaGVpZ2h0cyBtYXRjaCB0aGUgb3JpZ2luYWwgcmVsaWVmLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgaW4gTHVrYSYjMzk7cyByZWxpZWYuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBoPHN1Yj5pPFwvc3ViPiAoLTEgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEwIDAwMCksIHRoZSBjb2x1bW4gaGVpZ2h0cy4gQSBoZWlnaHQgb2YgLTEgcmVwcmVzZW50cyBhIHN0b2xlbiBjb2x1bW4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHBvc3NpYmxlIHJlbGllZnMgbW9kdWxvIDEgMDAwIDAwMCAwMDcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #6 5번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: chansol