Rescuing the Princess

Dario and Princess Orange were enjoying a quiet picnic on Yusi Island. While Dario was away for a moment, the villain Hooper kidnapped the princess and fled. Dario sets out for Hooper Island, where the princess is being held.

To travel from Yusi Island to Hooper Island, Dario must pass through several islands. All islands, including Yusi Island and Hooper Island, lie on one straight line passing through those two islands. In the picture, the scale below each circular island shows how many kilometers that island is from Yusi Island. The leftmost island is Yusi Island, and Hooper Island is the farthest island, 15 km away.

To move from one island to another, Dario must step on the springboard on his current island and jump. Each springboard is fragile and breaks after it is used once. Therefore, every island except the starting island, Yusi Island, must not be visited more than once.

The springboards have different strengths. The number written inside an island is the farthest distance that Dario can reach with that island's springboard. For example, if the island 7 km from Yusi Island has spring strength 3, then Dario can jump from it to any island whose distance from Yusi Island is between 4 km and 10 km, inclusive.

Before rescuing the princess, Dario runs only toward Hooper Island and always jumps in that direction. After rescuing her, he carries her on his back and escapes only toward Yusi Island.

Some springboards are so weak that they break as soon as Dario steps on them while carrying the princess. The gray island 12 km from Yusi Island in the picture is such an example. These springboards can be used only on the way to Hooper Island.

Given the information about all islands, including Yusi Island and Hooper Island, and the springboard on each island, write a program that outputs the number of different routes that start from Yusi Island, rescue the princess, and return, modulo 1000.

The first line contains the number of islands N. This count includes Yusi Island and Hooper Island, and 3 <= N <= 500.

Each of the next N lines contains the information for one island. The islands are given in increasing order of distance from Yusi Island. Therefore, the first island is always Yusi Island, and the last island is always Hooper Island.

Each island line contains three integers separated by spaces.

The first integer is the island's distance from Yusi Island. This value is 0 for Yusi Island, and it is largest for Hooper Island. Each distance is between 0 and 100000, inclusive, and no two islands have the same distance.

The second integer is the strength of the island's springboard: the maximum distance left or right that Dario can jump from that island. This value is between 1 and 1000, inclusive.

The third integer indicates whether the springboard can also be used while Dario is carrying Princess Orange. It is 1 if it can be used with the princess, and 0 otherwise. For Hooper Island, this value is always 1.

Print one integer: the number of routes that start from Yusi Island, rescue Princess Orange, and return, modulo 1000.