정올국 국방부는 수도 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→R1→B, A→R2→B, A→R3→B의 세 가지 독립적인 경로에 있어서

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

전파기지국 timer 3s memory 256MB

전파기지국 3s 256MB