시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 386 172 126 43.902%

문제

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

모든 문제의 난이도는 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+XHJcblx0XHVjNzc0IFx1YjU0YywgXHViYjM4XHVjODFjXHViOTdjIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM1YjRcdWI1YTQgXHViMDljXHVjNzc0XHViM2M0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWFjMDAgXHViMmU0XHViOTc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWI0NTAgXHViYzI5XHViYzk1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MTVcdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE4gKDIgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDEwPHN1cD45PFwvc3VwPlx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIGlcdWM3NzggXHViYjM4XHVjODFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAxMDxzdXA+OTxcL3N1cD5cdWI5N2MgXHViMTE4XHVjOWMwXHVjNTRhXHViMjk0IE4tMVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCBcdWIwOWNcdWM3NzRcdWIzYzRcdWFjMDAgaSBcdWI2MTBcdWIyOTQgaSsxXHVjNzc4IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIT05JIiwiZGVzY3JpcHRpb24iOiI8cD5Gcm9tIGEgcGlsZSBvZiBzdWdnZXN0ZWQgdGFza3MsIGF1dGhvcnMgb2YgQ09DSSBtdXN0IGNob29zZSBvbmVzIHRoYXQgd2lsbCBhcHBlYXIgaW4gdGhlIG5leHQgcm91bmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkRpZmZpY3VsdHkgb2YgYSB0YXNrIGlzIGRlc2NyaWJlZCB3aXRoIGFuIGludGVnZXIgaW4gcmFuZ2UgMSB0byBOLiBGb3Igc29tZSB0YXNrcywgaG93ZXZlciwgaXQmcnNxdW87cyBub3QgZWFzeSB0byBleGFjdGx5IGRldGVybWluZSB0aGVpciBkaWZmaWN1bHR5LiBBdXRob3JzIG9mIENPQ0kgZGVjaWRlZCB0aGF0IHRoZXNlIHRhc2tzIGNhbiBiZSBjb25zaWRlcmVkIGFzIGhhdmluZyBlaXRoZXIgb25lIG9mIHR3byBjb25zZWN1dGl2ZSBkaWZmaWN1bHRpZXMuIEZvciBleGFtcGxlLCBzb21lIHRhc2sgY2FuIGJlIGNvbnNpZGVyZWQgYXMgaGF2aW5nIGRpZmZpY3VsdHkgb2YgZWl0aGVyIDMgb3IgNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgcm91bmQgb2YgQ09DSSB3aWxsIGNvbnRhaW4gZXhhY3RseSBOIHRhc2tzLiBGb3IgZWFjaCBkaWZmaWN1bHR5LCB0aGVyZSB3aWxsIGJlIGV4YWN0bHkgb25lIHRhc2sgd2l0aCB0aGF0IGRpZmZpY3VsdHkuIE9mIGNvdXJzZSwgbm8gdGFzayB3aWxsIGFwcGVhciB0d2ljZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIGF1dGhvcnMgY2FuIGNob29zZSB0YXNrcyBmb3IgdGhlIG5leHQgcm91bmQuIFdlIHNheSB0aGF0IHR3byB3YXlzIGFyZSBkaWZmZXJlbnQgaWYgZm9yIHNvbWUgZGlmZmljdWx0eSwgYSBkaWZmZXJlbnQgdGFzayBpcyBhc3NpZ25lZCB0byB0aGF0IGRpZmZpY3VsdHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNpbmNlIHRoZSBleHBlY3RlZCByZXN1bHQgY2FuIGJlIHZlcnkgbGFyZ2UsIG91dHB1dCB0aGUgbnVtYmVyIG9mIHdheXMgbW9kdWxvIDEgMDAwIDAwMCAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBpbnRlZ2VycyBub3QgZ3JlYXRlciB0aGFuIDEwPHN1cD45PFwvc3VwPi4gaS10aCBudW1iZXIgaW4gdGhpcyBsaW5lIGlzIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgdGFza3MgaW4gYSBwaWxlIGhhdmluZyBkaWZmaWN1bHR5IGV4YWN0bHkgaS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTi0xIGludGVnZXJzIG5vdCBncmVhdGVyIHRoYW4gMTA8c3VwPjk8XC9zdXA+LiBpLXRoIG51bWJlciBpbiB0aGlzIGxpbmUgaXMgZXF1YWwgdG8gdGhlIG51bWJlciBvZiB0YXNrcyBpbiBhIHBpbGUgaGF2aW5nIGRpZmZpY3VsdHkgZWl0aGVyIGkgb3IgaSsxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG51bWJlciBvZiB3YXlzIG1vZHVsbyAxIDAwMCAwMDAgMDA3LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=