시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB69029821143.149%

문제

상근이는 서강 프로그래밍 대회의 문제를 준비해야 한다.

모든 문제의 난이도는 1과 N사이의 자연수로 표현할 수 있다. 하지만, 어떤 문제는 난이도를 정확하게 결정할 수 없는 경우도 있다. 따라서, 상근이는 문제의 난이도를 숫자 하나 또는 연속한 두 수로 표현하기로 했다. 예를 들어, 어떤 문제의 난이도는 3 또는 4가 될 수 있다.

올해 대회는 총 N문제가 필요하다. 상근이는 각 난이도에 해당하는 문제를 한 문제씩 내기로 했다. 당연하겠지만 같은 문제를 두 번 낼 수는 없다.

이때, 문제를 고르는 경우의 수를 구하는 프로그램을 작성하시오. 어떤 난이도에 해당하는 문제가 다른 경우에 두 방법이 서로 다른 경우이다.

정답이 매우 커질 수 있으므로 경우의 수를 1,000,000,007로 나눈다.

입력

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 109를 넘지 않는 N개의 정수가 주어진다. i번째 수는 난이도가 i인 문제의 개수이다.

셋째 줄에는 109를 넘지않는 N-1개의 정수가 주어진다. i번째 수는 난이도가 i 또는 i+1인 문제의 개수이다.

출력

첫째 줄에 문제를 고를 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
3 0 1
0 1

예제 출력 1

3

예제 입력 2

4
1 5 3 0
0 2 1

예제 출력 2

33
W3sicHJvYmxlbV9pZCI6IjI4NTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM4MWMgXHVjZDljXHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTFjXHVhYzE1IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWM3NTggXHViYjM4XHVjODFjXHViOTdjIFx1YzkwMFx1YmU0NFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWJiMzhcdWM4MWNcdWM3NTggXHViMDljXHVjNzc0XHViM2M0XHViMjk0IDFcdWFjZmMgTlx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNWI0XHViNWE0IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIwOWNcdWM3NzRcdWIzYzRcdWI5N2MgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWIwOWNcdWM3NzRcdWIzYzRcdWI5N2MgXHVjMjJiXHVjNzkwIFx1ZDU1OFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVjNWYwXHVjMThkXHVkNTVjIFx1YjQ1MCBcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNWI0XHViNWE0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWIwOWNcdWM3NzRcdWIzYzRcdWIyOTQgMyBcdWI2MTBcdWIyOTQgNFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjJjXHVkNTc0IFx1YjMwMFx1ZDY4Y1x1YjI5NCBcdWNkMWQgTlx1YmIzOFx1YzgxY1x1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHViMDljXHVjNzc0XHViM2M0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNTVjIFx1YmIzOFx1YzgxY1x1YzUyOSBcdWIwYjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWIyZjlcdWM1ZjBcdWQ1NThcdWFjYTBcdWM5YzBcdWI5Y2MgXHVhYzE5XHVjNzQwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI0NTAgXHViYzg4IFx1YjBiYyBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWFjZTBcdWI5NzRcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNWI0XHViNWE0IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViNDUwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHViMmY1XHVjNzc0IFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOICgyICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAxMDxzdXA+OTxcL3N1cD5cdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YWMwMCBpXHVjNzc4IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMTA8c3VwPjk8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMFx1YzU0YVx1YjI5NCBOLTFcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIGkgXHViNjEwXHViMjk0IGkrMVx1Yzc3OCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHViOTdjIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSE9OSSIsImRlc2NyaXB0aW9uIjoiPHA+RnJvbSBhIHBpbGUgb2Ygc3VnZ2VzdGVkIHRhc2tzLCBhdXRob3JzIG9mIENPQ0kgbXVzdCBjaG9vc2Ugb25lcyB0aGF0IHdpbGwgYXBwZWFyIGluIHRoZSBuZXh0IHJvdW5kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5EaWZmaWN1bHR5IG9mIGEgdGFzayBpcyBkZXNjcmliZWQgd2l0aCBhbiBpbnRlZ2VyIGluIHJhbmdlIDEgdG8gTi4gRm9yIHNvbWUgdGFza3MsIGhvd2V2ZXIsIGl0JnJzcXVvO3Mgbm90IGVhc3kgdG8gZXhhY3RseSBkZXRlcm1pbmUgdGhlaXIgZGlmZmljdWx0eS4gQXV0aG9ycyBvZiBDT0NJIGRlY2lkZWQgdGhhdCB0aGVzZSB0YXNrcyBjYW4gYmUgY29uc2lkZXJlZCBhcyBoYXZpbmcgZWl0aGVyIG9uZSBvZiB0d28gY29uc2VjdXRpdmUgZGlmZmljdWx0aWVzLiBGb3IgZXhhbXBsZSwgc29tZSB0YXNrIGNhbiBiZSBjb25zaWRlcmVkIGFzIGhhdmluZyBkaWZmaWN1bHR5IG9mIGVpdGhlciAzIG9yIDQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IHJvdW5kIG9mIENPQ0kgd2lsbCBjb250YWluIGV4YWN0bHkgTiB0YXNrcy4gRm9yIGVhY2ggZGlmZmljdWx0eSwgdGhlcmUgd2lsbCBiZSBleGFjdGx5IG9uZSB0YXNrIHdpdGggdGhhdCBkaWZmaWN1bHR5LiBPZiBjb3Vyc2UsIG5vIHRhc2sgd2lsbCBhcHBlYXIgdHdpY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyBhdXRob3JzIGNhbiBjaG9vc2UgdGFza3MgZm9yIHRoZSBuZXh0IHJvdW5kLiBXZSBzYXkgdGhhdCB0d28gd2F5cyBhcmUgZGlmZmVyZW50IGlmIGZvciBzb21lIGRpZmZpY3VsdHksIGEgZGlmZmVyZW50IHRhc2sgaXMgYXNzaWduZWQgdG8gdGhhdCBkaWZmaWN1bHR5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGUgZXhwZWN0ZWQgcmVzdWx0IGNhbiBiZSB2ZXJ5IGxhcmdlLCBvdXRwdXQgdGhlIG51bWJlciBvZiB3YXlzIG1vZHVsbyAxIDAwMCAwMDAgMDA3LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgbm90IGdyZWF0ZXIgdGhhbiAxMDxzdXA+OTxcL3N1cD4uIGktdGggbnVtYmVyIGluIHRoaXMgbGluZSBpcyBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHRhc2tzIGluIGEgcGlsZSBoYXZpbmcgZGlmZmljdWx0eSBleGFjdGx5IGkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4tMSBpbnRlZ2VycyBub3QgZ3JlYXRlciB0aGFuIDEwPHN1cD45PFwvc3VwPi4gaS10aCBudW1iZXIgaW4gdGhpcyBsaW5lIGlzIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgdGFza3MgaW4gYSBwaWxlIGhhdmluZyBkaWZmaWN1bHR5IGVpdGhlciBpIG9yIGkrMS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgb2Ygd2F5cyBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #5 4번