JOI is a boy who loves observing the starry sky. Every night, he observes the stars and enjoys figuring out which constellation each star belongs to.

One night, while observing the sky as usual, JOI discovered $N$ stars he had never seen before. Curious about which constellations these stars belong to, he took a photograph of the night sky and researched these stars at the library the next day. He found that all these stars belong to either constellation A or constellation B, and for some of these stars, he knew which constellation they belonged to. However, for the other stars, he did not know which constellation they belonged to. JOI became interested in how many possible ways there are to form the sets of stars that make up constellation A and constellation B. Note that the stars are small enough to be considered points.

A constellation consists of one or more stars and several line segments connecting two stars, satisfying the following conditions. Note that a constellation consisting of only one star is also considered a constellation.

• Any two stars forming a constellation can reach each other by following the line segments that make up that constellation on the photograph.
• Line segments forming one constellation do not intersect with line segments forming another constellation.

Also, the stars discovered by JOI satisfy the following conditions:

• No three stars are collinear on the photograph.
• Every star belongs to either constellation A or constellation B, and there are no stars belonging to constellation A or constellation B other than those discovered by JOI.

Input

Read the following from standard input:

• The first line contains an integer $N$, representing the number of stars discovered by JOI.
• The following $N$ lines contain information about the stars. The $(i+1)$-th line ($1 \le i \le N$) contains three integers $X_i, Y_i, C_i$ separated by spaces. $X_i$ and $Y_i$ represent the coordinates of star $i$ on the photograph $(X_i, Y_i)$. $C_i$ represents which constellation star $i$ belongs to.
  • If $C_i = 0$, it means it is unknown which constellation star $i$ belongs to.
  • If $C_i = 1$, it means star $i$ belongs to constellation A.
  • If $C_i = 2$, it means star $i$ belongs to constellation B.

Output

Output the total number of possible ways to form the sets of stars for constellation A and constellation B, modulo $1\,000\,000\,007$ ($= 10^9 + 7$), in a single line. If no such set of stars exists, output 0.

Constraints

• $2 \le N \le 100\,000$
• $0 \le X_i \le 10^9, 0 \le Y_i \le 10^9$

Subtasks

• For 10% of the test cases, $N \le 10$.
• For 50% of the test cases, $N \le 300$.

Examples

Input 1

4
1 1 1
2 1 1
1 2 0
2 2 2

Output 1

2

Note

This input example corresponds to the following figure. Black dots represent stars belonging to constellation A, white dots represent stars belonging to constellation B, and the $\times$ mark represents a star whose constellation is unknown.

The answer for this input is 2, corresponding to the cases where star 3 belongs to constellation A and where it belongs to constellation B. Examples of the constellation diagrams for each case are shown below. Note that when star 3 belongs to constellation A, there may be multiple ways to draw the line segments for constellation A, but all of them are counted as 1 way.

When star 3 belongs to constellation A (left) and when star 3 belongs to constellation B (right)