Radek and Friends Flooding

This problem is based on the following scenario: The company Radek and Friends wants to flood the shelves of its competitor Mati and Company by activating water faucets mounted above the shelves. Each shelf is represented by a horizontal line segment between the points \((l_i, h_i)\) and \((r_i, h_i)\), and a water faucet is installed at the point \( \left(\frac{l_i+r_i}{2}, \; h_i+0.5\right)\).

When the faucet above shelf \(i\) is opened, the shelf is immediately flooded. Then, water starts dripping vertically downward from the two endpoints \((l_i, h_i)\) and \((r_i, h_i)\) of that shelf. For each drip, the water falls straight down until it hits a shelf below. Formally, for a drip falling at \(x\) (which is either \(l_i\) or \(r_i\)) from a height of \(h_i\), let \(F(x, h_i)\) be defined as the shelf \(j\) with \(h_j < h_i\) such that \(x \in [l_j, r_j]\) and \(h_j\) is the largest possible (i.e. the first shelf encountered by the water). If such a shelf exists, then that shelf will be flooded and it in turn will generate two new drips from its endpoints. Otherwise, the water falls onto the ground (the \(OX\) axis).

Radek will inspect the faucets in some order. When he encounters the faucet above shelf \(i\), he will open it if and only if shelf \(i\) is not yet flooded by water dripping down from a previously opened faucet. Before he starts, the order in which he inspects all \(n\) faucets is chosen uniformly at random among all \(n!\) possibilities.

Your task is to compute the expected number of faucets that Radek will open. It can be proved that this expected value is a rational number, say \(\frac{p}{q}\) in lowest terms, and that \(q\) is not divisible by \(10^9+7\). You need to output \(p \cdot q^{-1} \pmod{10^9+7}\), where \(q^{-1}\) is the modular inverse of \(q\) modulo \(10^9+7\). In other words, if the answer is \(\frac{p}{q}\), output \[ p \cdot q^{-1} \pmod{10^9+7}. \]

Observation: When a shelf receives water from another shelf (via one of the two drips), it will not have its faucet opened when inspected later. In any connected chain of shelves (determined by the dripping process) exactly the faucet of the earliest inspected shelf (among those in the chain) is opened. This leads to the fact that the probability that a given shelf \(i\) has its faucet opened is \(\frac{1}{d_i+1}\), where \(d_i\) is the number of shelves that can drip water onto shelf \(i\) (i.e. the number of distinct predecessors in the dripping process). Thus, the expected number of faucets opened is the sum over all shelves of \(\frac{1}{d_i+1}\).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 2000\)), the number of shelves.

Each of the next \(n\) lines contains three integers \(l_i\), \(r_i\) and \(h_i\) representing the left coordinate, right coordinate and the height of shelf \(i\), respectively. It is guaranteed that \(l_i < r_i\) and that the shelves are placed in the plane.

outputFormat

Output a single integer: the expected number of faucets Radek will open, computed as \(p \cdot q^{-1} \pmod{10^9+7}\) where the expected value is \(\frac{p}{q}\) in lowest terms.

sample

1
0 10 5

1