시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 143 33 29 36.709%

문제

취미로 게임 만드는 걸 좋아하는 현욱은 오늘 간단한 게임 기획을 하나 떠올렸다. 현욱이 생각한 게임에는 N개의 레벨이 있는데, 각 레벨을 클리어하면 플레이어는 일정량의 점수를 획득할 수 있다. 또, 각 레벨은 클리어 후 진행할 수 있는 다음 레벨이 몇 종류 정해져있고, 플레이어는 그 레벨들 중 하나를 골라 해당 레벨로 진행할 수 있다.

현욱이 만든 게임의 기획을 요약하면 다음과 같다.

  1. 시작 레벨이 하나 존재한다.
  2. 시작 레벨에서 다른 레벨에 도달할 수 있는 방법은 항상 존재하며 유일하다.
  3. 플레이어는 각 레벨을 클리어시 Si점을 획득할 수 있다.
  4. 레벨 별로 Ki점이 주어지는데, 이는 기획자가 의도한 해당 레벨을 클리어하고 난 후 플레이어의 누적 점수합이다.
  5. 레벨 i가 레벨 j보다 이후에 클리어해야 하는 레벨이라면 반드시 Si > Sj여야한다. 즉, 클리어시 획득하는 점수가 증가하는 방향으로만 게임이 진행돼야 한다.

현욱은 기획을 끝내고 나서 문득, 위의 조건을 만족하는 레벨 배치를 얼마나 다양하게 만들 수 있을 지 궁금해졌다. 현욱을 도와 주어진 Si, Ki 수치 조건을 만족하게 모든 레벨을 배치할 수 있는 경우의 수를 모두 구하는 프로그램을 작성해보자.

입력

첫 줄에 레벨의 개수 N(1 ≤ N ≤ 3 * 105)이 주어진다. 둘째 줄에 각 레벨에 대한 Si(1 ≤ Si ≤ 109)가 주어진다. 셋쩨 줄에 각 레벨에 대한 Ki(1 ≤ Ki ≤ 109)가 주어진다.

출력

첫째 줄에 주어진 Si, Ki값을 만족하게 레벨을 배치할 수 있는 경우의 수를 109 + 7로 나눈 나머지를 출력한다. 각 레벨 배치에서 모든 레벨에 대해, 그 레벨을 클리어한 후 진행할 수 있는 다음 레벨 목록이 동일하다면(순서는 상관 없음), 두 배치는 동일한 배치로 생각한다.

예제 입력 1

3
2 6 4
2 8 6

예제 출력 1

1

예제 입력 2

3
2 1 3
2 3 4

예제 출력 2

0

힌트

첫 번째 입력에서, 조건을 만족하는 배치는 시작 레벨이 1레벨이고, 1레벨을 클리어한 후 2,3레벨 중 하나를 골라 진행할 수 있는 배치 하나 밖에 없다. 두 번째 입력에서 조건을 만족하게 배치할 수 있는 방법은 존재하지 않는다.

출처

Contest > 소프트콘 > 제1회 소프트콘 C번