It’s Halloween, and you’ve organized a bonfire and dance for the neighborhood children. The $n$ children have gathered into a ring to dance around the fire. Each child is wearing one of two fun yet spooky costumes: orange pumpkin, or black bat. Since it’s dark outside, you can only see a few children at a time, as they pass behind the bonfire. The children are not standing evenly so the number of children you can see at each time differs. In particular, numbering the children $0, 1, \ldots , n-1$ clockwise around the dance circle, at any given time you can see child $i$ in the center of your view, as well as $l_ i$ children before child $i$ and $r_ i$ children after child $i$ around the circle (i.e., child $i-l_ i, \ldots , i-1, i, i+1, \ldots , i+r_ i$, where the indices are of course taken modulo $n$).

To help pass the time while the children dance, you wonder to yourself: suppose you only knew, for each child $i$, whether an even or odd number of the $l_ i+r_ i+1$ children centered at child $i$ is wearing the orange pumpkin costume. Would you be able to uniquely reconstruct what costume each child is wearing? Clearly this is possible when $l_ i=r_ i=0$. But what if $l_ i$ and $r_ i$ are not always zero? Maybe there are multiple possible solutions, or none at all? You decide to investigate, later in the evening once you’re back at your computer.

-----Input-----
The first line of the input consists of a single integer $n$, indicating that there are $n$ children in the ring $(1 \leq n \leq 200000)$. The following $n$ lines describe the children you can see at different times. The $i$th line (indexed starting from zero) contains three space-separated non-negative integers $l_ i$, $r_ i$, $x_ i$ ($l_ i+r_ i+1\leq n,0\leq x_ i\leq 1$): you can see $l_ i+r_ i+1$ children when child $i$ is in the center of view ($l_ i$ to the left and $r_ i$ to the right of child $i$). If $x_ i=0$ then an even number of them are wearing the orange pumpkin costume. If $x_ i=1$ then an odd number of them are wearing the orange pumpkin costume.

-----Output-----
Compute the number of ways of assigning a costume to each child, consistent with your observations. Since this number might be large, print the result modulo $10^9 + 7$. (If it’s impossible to find any costume assignment that matches all parity constraints, print 0).

-----Examples-----
Sample Input:
5
1 0 0
1 0 1
3 0 1
3 0 0
3 0 1
Sample Output:
0

见题面

见题面