Bessie는 길이 $N$ ($1\le N\le500$) 배열 둘이 있습니다. 첫 배열 $i$번째 $a_i$ ($1\le a_i\le10^6$), 둘째 $b_i$ ($1\le b_i\le10^6$)입니다.

둘을 비어 있지 않은 부분 배열로 나눠 조건을 만족하려 합니다:

1. 모든 원소는 정확히 하나에 속합니다.
2. 둘 다 같은 $k$개로 나눕니다.
3. 모든 $1\le i\le k$에서 왼쪽 $i$번째 첫 배열 부분 평균이 둘째의 해당 평균 이하입니다.

방법 수를 $10^9+7$로 나눈 나머지를 구하세요. 부분 수가 다르거나 원소가 다른 부분에 속하면 다릅니다.

입력

첫 줄 $N$.

다음 $a_1,a_2,\ldots,a_N$.

다음 $b_1,b_2,\ldots,b_N$.

출력

조건을 만족하는 비어 있지 않은 부분 배열 분할 수를 $10^9+7$로 나눈 나머지.

예제

입력 1

2
1 2
2 2

출력 1

2

참고

두 방법, 첫 배열과 둘째 배열 순서:

1. $[1],[2]$ / $[2],[2]$.
2. $[1,2]$ / $[2,2]$.

입력 2

3
1 3 2
2 2 2

출력 2

3

참고

세 방법, 첫 배열과 둘째 배열 순서:

1. $[1,3],[2]$ / $[2,2],[2]$.
2. $[1,3],[2]$ / $[2],[2,2]$.
3. $[1,3,2]$ / $[2,2,2]$.

입력 3

5
2 5 1 3 2
2 1 5 2 2

출력 3

1

참고

유일한 방법, 첫 배열과 둘째 배열 순서: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

입력 4

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

출력 4

140

서브태스크

• 입력 5–6: $N\le10$.
• 입력 7–9: $N\le80$.
• 입력 10–17: $N\le300$.
• 입력 18–20: $N\le500$.

문제 작성: Alex Liang