레이팅 미적용설명
베시에게 길이 \(N\)(\(1 \le N \le 500\))의 배열이 두 개 있다. 첫 번째 배열의 \(i\)번째 원소는 \(a_i\)(\(1 \le a_i \le 10^6\))이고, 두 번째 배열의 \(i\)번째 원소는 \(b_i\)(\(1 \le b_i \le 10^6\))이다.
베시는 다음 조건을 만족하도록 두 배열을 모두 비어 있지 않은 부분 배열들로 나누고 싶다.
- 모든 원소는 정확히 1개의 부분 배열에 속한다.
- 두 배열은 같은 개수의 부분 배열로 나뉜다. 첫 번째와 두 번째 배열이 나뉜 부분 배열의 개수를 \(k\)라 하자 (즉, 첫 번째 배열은 정확히 \(k\)개의 부분 배열로, 두 번째 배열도 정확히 \(k\)개의 부분 배열로 나뉜다).
- 모든 \(1 \le i \le k\)에 대해, 첫 번째 배열의 왼쪽에서 \(i\)번째 부분 배열의 평균은 두 번째 배열의 왼쪽에서 \(i\)번째 부분 배열의 평균보다 작거나 같다.
조건을 만족하면서 두 배열을 비어 있지 않은 부분 배열들로 나누는 방법의 수를 \(10^9+7\)로 나눈 나머지를 구하여라. 부분 배열의 개수가 다르거나 어떤 원소가 서로 다른 부분 배열에 속하면 두 방법은 서로 다른 것으로 간주한다.
문제 제공: Alex Liang
제약
배점
- 입력 5-6: \(N \le 10\)
- 입력 7-9: \(N \le 80\)
- 입력 10-17: \(N \le 300\)
- 입력 18-20: \(N \le 500\)
문제 제공: Alex Liang
입력 형식
첫째 줄에 \(N\)이 주어진다.
다음 줄에 \(a_1,a_2,...,a_N\)이 주어진다.
다음 줄에 \(b_1,b_2,...,b_N\)이 주어진다.
출력 형식
조건을 만족하면서 두 배열을 비어 있지 않은 부분 배열들로 나누는 방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
예제 1
입력
2
1 2
2 2출력
2설명
The two valid ways are:
- Split the first array into \([1],[2]\) and the second array into \([2],[2]\).
- Split the first array into \([1,2]\) and the second array into \([2,2]\).
예제 2
입력
3
1 3 2
2 2 2출력
3설명
The three valid ways are:
- Split the first array into \([1,3],[2]\) and the second array into \([2,2],[2]\).
- Split the first array into \([1,3],[2]\) and the second array into \([2],[2,2]\).
- Split the first array into \([1,3,2]\) and the second array into \([2,2,2]\).
예제 3
입력
5
2 5 1 3 2
2 1 5 2 2출력
1설명
The only valid way is to split the first array into \([2],[5,1,3],[2]\) and the
second array into \([2],[1,5],[2,2]\).
예제 4
입력
7
3 5 2 3 4 4 1
5 3 5 3 3 4 1출력
140문제 정보
태그