Background

Note: For the original problem (Java), the time limit is 3.0 s and the memory limit is 512 MB.

Problem Description

In the mysterious ancient forest of LQ Kingdom, there is a mysterious ruin called “Build a Cross”. It is said that “Build a Cross” was built by an ancient civilization. It is a huge stone structure formed by stacking two large rectangles so that they cross each other, creating a solemn and mysterious cross shape.

Now you are given $N$ rectangles. For the $i$-th rectangle, its length and width are $l_i$ and $w_i$, and its color $c_i$ is one of red $(0)$, yellow $(1)$, or blue $(2)$. Now Xiaolan wants to know how many pairs among these $N$ rectangles can “build a cross”.

Two rectangles can “build a cross” if and only if:

1. The two rectangles have different colors.
2. Rectangle $1$ has a strictly greater length than rectangle $2$, and rectangle $1$ has a strictly smaller width than rectangle $2$.

Note that the length and width of a rectangle are fixed and cannot be swapped by rotating the rectangle.

Input Format

The first line contains an integer $N$, meaning there are $N$ rectangles.

The next $N$ lines each contain three integers $l$, $w$, and $c$, representing the length, width, and color of a rectangle.

Output Format

Output one integer, the answer. Since the answer may be very large, output it modulo $10^9 + 7$.

5
1 10 0
6 6 0
8 6 1
6 10 0
1 2 1

2

Hint

[Sample Explanation]

The 3rd rectangle can build a cross with the 1st rectangle, and the 3rd rectangle can also build a cross with the 4th rectangle. So there are 2 pairs of rectangles that can build a cross, and the answer is $2$.

[Constraints]

• For $30\%$ of the testdata: $1 \leq N \leq 5000$.
• For $100\%$ of the testdata: $1 \leq N \leq 10^5$, $1 \leq l,w \leq 10^5$, $0 \leq c \leq 2$.

Translated by ChatGPT 5