문제
정올 모의고사 담당자 정쌤은 모아둔 여러 개의 문제들에서 다음 모의고사에 낼 문제를 골라야한다. 각 문제의 난이도는 1부터 N으로써 표현되어있다. 그러나 하나의 난이도로 결정짓기 난해한 문제는 때에 따라서 두 가지의 난이도로 쓰일 수 있다. 예를 들어 어떤 문제는 경우에 따라 난이도 3과 4 둘 중 하나로 표현 될 수 있다.
정올 모의고사의 다음 시험에는 N개의 서로 다른 난이도의 문제가 출제 되어야 한다. 물론, 하나의 문제가 두 번 나올 수 없다.
다음 시험에 출제될 문제들의 경우의 수를 찾아라. 결과가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력하라.
입력
첫 번째 줄은 N(2≤N≤100000)이 입력된다.
두 번째 줄은 109을 넘지 않는 정수가 N개 입력된다. 이 줄의 i번째 숫자는 난이도가 i인 문제의 수이다.
세 번째 줄은 109을 넘지 않는 정수가 N-1개 입력된다. 이 줄의 i번째 숫자는 난이도가 i또는 i+1가 될 수 있는 문제의 수이다.
출력
출제 가능한 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제 #1
3
3 0 1
0 1
3
예제 #2
4
1 5 3 0
0 2 1
33
출처
COCI 2010/2011 contest5 4
로그인해야 코드를 작성할 수 있어요.