공주 구하기

유시 섬에서 소풍을 즐기던 다리오와 오렌지 공주에게 사건이 일어났다. 다리오가 잠시 자리를 비운 사이, 악당 후퍼가 공주를 데리고 달아났다. 다리오는 공주가 숨겨진 후퍼 섬으로 향한다.

유시 섬에서 후퍼 섬까지 가려면 중간의 여러 섬을 거쳐야 한다. 유시 섬과 후퍼 섬을 포함한 모든 섬은 두 섬을 지나는 하나의 직선 위에 있다. 그림에서 각 섬 아래의 눈금자는 그 섬이 유시 섬에서 몇 km 떨어져 있는지를 나타낸다. 가장 왼쪽 섬이 유시 섬이고, 가장 멀리 있는 후퍼 섬은 15 km 떨어져 있다.

한 섬에서 다른 섬으로 이동하려면 현재 섬에 하나씩 있는 스프링 발판을 밟아 점프해야 한다. 스프링 발판은 내구성이 약해서 한 번 사용하면 부서진다. 따라서 출발점인 유시 섬을 제외한 모든 섬은 두 번 이상 방문할 수 없다.

스프링 발판의 세기는 섬마다 다르다. 섬을 나타내는 원 안의 숫자는 그 섬의 스프링 발판을 밟았을 때 도달할 수 있는 최대 거리를 뜻한다. 예를 들어 유시 섬에서 7 km 떨어진 섬의 스프링 발판 세기가 3이라면, 유시 섬에서의 거리가 4 km 이상 10 km 이하인 섬으로 점프할 수 있다.

공주를 구하기 전까지 다리오는 후퍼 섬 방향으로만 이동한다. 공주를 구한 뒤에는 공주를 업고 유시 섬 방향으로만 되돌아온다.

일부 스프링 발판은 너무 약해서 공주를 업은 상태에서는 밟는 순간 부서진다. 그림에서 유시 섬에서 12 km 떨어진 회색 섬의 스프링 발판이 그런 경우이다. 이런 발판은 후퍼 섬으로 공주를 구하러 갈 때에만 사용할 수 있다.

유시 섬과 후퍼 섬을 포함한 모든 섬의 정보와 각 섬의 스프링 발판 정보가 주어진다. 다리오가 유시 섬을 출발해 공주를 구하고 다시 돌아오는 서로 다른 경로의 수를 1000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

첫째 줄에 섬의 개수 N이 주어진다. N에는 유시 섬과 후퍼 섬도 포함되며, 3 <= N <= 500이다.

다음 N개의 줄에는 각 섬의 정보가 한 줄에 하나씩 주어진다. 섬의 정보는 유시 섬과의 거리가 가까운 순서로 주어진다. 따라서 첫 번째 섬은 항상 유시 섬이고, 마지막 섬은 항상 후퍼 섬이다.

각 섬의 정보는 세 정수로 주어지며, 정수들은 공백으로 구분된다.

첫 번째 정수는 유시 섬에서 그 섬까지의 거리이다. 유시 섬의 값은 0이고, 후퍼 섬의 값이 가장 크다. 거리는 0 이상 100000 이하이며, 같은 거리를 가진 두 섬은 없다.

두 번째 정수는 스프링 발판의 세기이다. 이는 해당 섬에서 왼쪽이나 오른쪽으로 최대 얼마만큼 떨어진 섬까지 점프할 수 있는지를 나타낸다. 이 값은 1 이상 1000 이하이다.

세 번째 정수는 그 섬의 스프링 발판을 오렌지 공주를 업은 상태에서도 사용할 수 있는지를 나타낸다. 1이면 공주와 함께 사용할 수 있고, 0이면 사용할 수 없다. 후퍼 섬에서 이 값은 항상 1이다.

유시 섬에서 출발해 오렌지 공주를 구하고 돌아오는 전체 경로의 수를 1000으로 나눈 나머지를 출력한다.