페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3408

전파기지국 3s 256MB

문제

정올국 국방부는 수도 A부터 최전방 지역 B까지 무선 통신망을 설치하려 한다. 

A와 B는 수직선 상에 있고, A의 좌표는 0, B의 좌표는 M이다. 

A와 B사이엔, 전파기지국이 총 N-1개 있으며, A에도 전파기지국이 하나 있어 총 N개의 기지가 있고, 

B에서는 수신(신호를 받음)만 한다. 

각 전파기지국은 자신보다 오른쪽에 있는 기지에만 전파를 전달한다. 

또한, 각 전파기지국은 장비가 모두 달라서, 발신 세기가 모두 다르다. 

다른 전파기지에 신호를 전달하기 위해서는, 해당 기지와의 거리가 발신 세기보다 작거나 같아야만 한다.

국방부 장관 관영이는, 기밀 정보 1, 2, 3을 가지고 있다. 

관영이는 이 정보를 A에서 B까지 전달하는데 있어서, 세 가지의 독립적인 경로를 통해 신호 전달하려고 한다. 

독립적이라 함은, 신호 전달 경로가 A와 B를 제외하고는 어떤 전파기지국도 공유하지 않는 것이다. 

예를 들어, 1번부터 왼쪽에 있는 기지국이라고 할 때, 

A→​2→​3→​​5​→B와 A→​1→​4→​B 는 서로 독립적이지만, 

A→​3→​4→​5→​B와 A→​1→​4→​B는 독립적이지 않다.

각 기지국의 좌표와 발신 세기가 각각 주어졌을 때, 

세 가지의 독립적인 경로로 신호를 전달하는 방법의 수를 10억 7로 나눈 나머지를 구하는 프로그램을 작성하라.

유의사항: 기밀 정보 1, 2, 3이 서로 다르기 때문에, A→​R​1→​B, A→​R​2→​B, A→​R​3→​B의 세 가지 독립적인 경로에 있어서 

기밀 정보 1, 2, 3을 6가지 다른 방식으로 보낼 수 있다: (R1, R2, R3), (R1, R3, R2) … (R3, R2, R1). 

 

 


입력

첫 줄에 수도 A를 포함한 전파기지국의 개수인 N이 주어진다. (1<=N<=100) 다음 N줄에 걸쳐, 각 전파기지국의 위치와 발신 세기가 공백을 사이에 두고 주어진다. 입력은 항상 위치 기준으로 오름차순 정렬되어 주어진다. 전파기지국의 위치는 항상 서로 다르다. 첫 줄(전체적으로 보면 둘째 줄)은 수도 A의 기지국이므로, 위치가 항상 0으로 주어진다. 마지막 줄에 B의 위치인 M이 주어진다. (0<각 기지국의 좌표,M<1,000,000, 0<발신 세기<1,000,000) 부분점수 1: 25점에 해당하는 입력에 있어서 (1<=N<=10, 0<좌표, 발신 세기<100)을 만족하며 부분점수 2: 50점에 해당하는 입력에 있어서 (1<=N<=30, 0<좌표,발신 세기<1,000)을 만족한다.

출력

세 가지의 독립적인 경로로 신호를 전달하는 방법을 1,000,000,007로 나눈 나머지를 구한다.

예제 

7

0 4

1 6

3 3

4 9

6 6

7 2

9 3

10
6

출처

ohjtgood
로그인해야 코드를 작성할 수 있어요.