시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 395 175 129 43.581%

문제

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

모든 문제의 난이도는 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

4
1 5 3 0
0 2 1

예제 출력 1

33
W3sicHJvYmxlbV9pZCI6IjI4NTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM4MWMgXHVjZDljXHVjODFjIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzExY1x1YWMxNSBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHVjNzU4IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM5MDBcdWJlNDRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHViYjM4XHVjODFjXHVjNzU4IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YjI5NCAxXHVhY2ZjIE5cdWMwYWNcdWM3NzRcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzViNFx1YjVhNCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMDljXHVjNzc0XHViM2M0XHViOTdjIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWFjYjBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM3NTggXHViMDljXHVjNzc0XHViM2M0XHViOTdjIFx1YzIyYlx1Yzc5MCBcdWQ1NThcdWIwOTggXHViNjEwXHViMjk0IFx1YzVmMFx1YzE4ZFx1ZDU1YyBcdWI0NTAgXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzViNFx1YjVhNCBcdWJiMzhcdWM4MWNcdWM3NTggXHViMDljXHVjNzc0XHViM2M0XHViMjk0IDMgXHViNjEwXHViMjk0IDRcdWFjMDAgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYyY1x1ZDU3NCBcdWIzMDBcdWQ2OGNcdWIyOTQgXHVjZDFkIE5cdWJiMzhcdWM4MWNcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAxIFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM1MjkgXHViMGI0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHViMmY5XHVjNWYwXHVkNTU4XHVhY2EwXHVjOWMwXHViOWNjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViNDUwIFx1YmM4OCBcdWIwYmMgXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHViNTRjLCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzViNFx1YjVhNCBcdWIwOWNcdWM3NzRcdWIzYzRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWIyZTRcdWI5NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjQ1MCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiAoMiAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMTA8c3VwPjk8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCBcdWIwOWNcdWM3NzRcdWIzYzRcdWFjMDAgaVx1Yzc3OCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDEwPHN1cD45PFwvc3VwPlx1Yjk3YyBcdWIxMThcdWM5YzBcdWM1NGFcdWIyOTQgTi0xXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YWMwMCBpIFx1YjYxMFx1YjI5NCBpKzFcdWM3NzggXHViYjM4XHVjODFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg1NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhPTkkiLCJkZXNjcmlwdGlvbiI6IjxwPkZyb20gYSBwaWxlIG9mIHN1Z2dlc3RlZCB0YXNrcywgYXV0aG9ycyBvZiBDT0NJIG11c3QgY2hvb3NlIG9uZXMgdGhhdCB3aWxsIGFwcGVhciBpbiB0aGUgbmV4dCByb3VuZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RGlmZmljdWx0eSBvZiBhIHRhc2sgaXMgZGVzY3JpYmVkIHdpdGggYW4gaW50ZWdlciBpbiByYW5nZSAxIHRvIE4uIEZvciBzb21lIHRhc2tzLCBob3dldmVyLCBpdCZyc3F1bztzIG5vdCBlYXN5IHRvIGV4YWN0bHkgZGV0ZXJtaW5lIHRoZWlyIGRpZmZpY3VsdHkuIEF1dGhvcnMgb2YgQ09DSSBkZWNpZGVkIHRoYXQgdGhlc2UgdGFza3MgY2FuIGJlIGNvbnNpZGVyZWQgYXMgaGF2aW5nIGVpdGhlciBvbmUgb2YgdHdvIGNvbnNlY3V0aXZlIGRpZmZpY3VsdGllcy4gRm9yIGV4YW1wbGUsIHNvbWUgdGFzayBjYW4gYmUgY29uc2lkZXJlZCBhcyBoYXZpbmcgZGlmZmljdWx0eSBvZiBlaXRoZXIgMyBvciA0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCByb3VuZCBvZiBDT0NJIHdpbGwgY29udGFpbiBleGFjdGx5IE4gdGFza3MuIEZvciBlYWNoIGRpZmZpY3VsdHksIHRoZXJlIHdpbGwgYmUgZXhhY3RseSBvbmUgdGFzayB3aXRoIHRoYXQgZGlmZmljdWx0eS4gT2YgY291cnNlLCBubyB0YXNrIHdpbGwgYXBwZWFyIHR3aWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgYXV0aG9ycyBjYW4gY2hvb3NlIHRhc2tzIGZvciB0aGUgbmV4dCByb3VuZC4gV2Ugc2F5IHRoYXQgdHdvIHdheXMgYXJlIGRpZmZlcmVudCBpZiBmb3Igc29tZSBkaWZmaWN1bHR5LCBhIGRpZmZlcmVudCB0YXNrIGlzIGFzc2lnbmVkIHRvIHRoYXQgZGlmZmljdWx0eS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIGV4cGVjdGVkIHJlc3VsdCBjYW4gYmUgdmVyeSBsYXJnZSwgb3V0cHV0IHRoZSBudW1iZXIgb2Ygd2F5cyBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGludGVnZXJzIG5vdCBncmVhdGVyIHRoYW4gMTA8c3VwPjk8XC9zdXA+LiBpLXRoIG51bWJlciBpbiB0aGlzIGxpbmUgaXMgZXF1YWwgdG8gdGhlIG51bWJlciBvZiB0YXNrcyBpbiBhIHBpbGUgaGF2aW5nIGRpZmZpY3VsdHkgZXhhY3RseSBpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOLTEgaW50ZWdlcnMgbm90IGdyZWF0ZXIgdGhhbiAxMDxzdXA+OTxcL3N1cD4uIGktdGggbnVtYmVyIGluIHRoaXMgbGluZSBpcyBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHRhc2tzIGluIGEgcGlsZSBoYXZpbmcgZGlmZmljdWx0eSBlaXRoZXIgaSBvciBpKzEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHdheXMgbW9kdWxvIDEgMDAwIDAwMCAwMDcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==