레벨 배치하기

시간 제한1초메모리 제한256 MB

요약

각 레벨의 클리어 점수 S_i와 시작 레벨에서 해당 레벨까지 누적 점수 K_i가 주어질 때, 부모보다 자식의 S가 큰 조건을 만족하는 레벨 배치의 수를 세는 문제입니다.

난이도: 어려움10점 중 8점
유형: 트리, 조합론, 정렬, DFS
정답자: 아직 제출이 없습니다

문제

취미로 게임을 만드는 현욱이 오늘 간단한 게임 기획을 하나 떠올렸다. 이 게임에는 레벨이 $N$ 개 있고, 플레이어는 레벨을 클리어할 때마다 정해진 점수를 얻는다. 레벨마다 클리어한 뒤 진행할 수 있는 다음 레벨이 몇 개씩 정해져 있으며, 플레이어는 그중 하나를 골라 진행한다.

기획을 정리하면 다음과 같다.

시작 레벨이 하나 있다.
시작 레벨에서 다른 레벨로 가는 방법은 항상 존재하고 유일하다.
레벨 $i$ 를 클리어하면 $S_i$ 점을 얻는다.
레벨 $i$ 에는 $K_i$ 가 함께 주어진다. 이 값은 기획자가 의도한, 레벨 $i$ 를 클리어한 직후의 누적 점수합이다. 즉 시작 레벨부터 레벨 $i$ 까지 거쳐 온 레벨의 점수를 모두 더한 값이다.
레벨 $i$ 를 레벨 $j$ 보다 나중에 클리어해야 한다면 반드시 $S_i > S_j$ 여야 한다. 게임은 클리어 점수가 커지는 방향으로만 진행된다.

기획을 끝낸 현욱은 위 조건을 만족하는 레벨 배치가 몇 가지나 되는지 궁금해졌다. 주어진 $S_i$ 와 $K_i$ 를 모두 만족하도록 레벨 $N$ 개를 배치하는 경우의 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 레벨의 개수 $N$ ( $1 \le N \le 3 \times 10^5$ )이 주어진다.

둘째 줄에 각 레벨의 $S_1, S_2, \dots, S_N$ ( $1 \le S_i \le 10^9$ )이 공백으로 구분되어 주어진다.

셋째 줄에 각 레벨의 $K_1, K_2, \dots, K_N$ ( $1 \le K_i \le 10^9$ )이 공백으로 구분되어 주어진다.

출력

첫째 줄에 주어진 $S_i$ , $K_i$ 를 만족하도록 레벨을 배치하는 경우의 수를 $10^9 + 7$ 로 나눈 나머지를 출력한다. 두 배치에서 모든 레벨의 다음 레벨 목록이 같으면(목록 안의 순서는 상관없다) 같은 배치로 본다.

힌트

첫 번째 예제에서 조건을 만족하는 배치는 하나뿐이다. 시작 레벨은 1번이고, 1번을 클리어한 뒤 2번과 3번 중 하나를 골라 진행한다. 두 번째 예제에서는 조건을 만족하는 배치가 없다.

예제2

예제 1
입력
```
3
2 6 4
2 8 6
```
예상 출력
```
1
```
예제 2
입력
```
3
2 1 3
2 3 4
```
예상 출력
```
0
```