Problem D
Dance Circle

Children Dancing in a Ring by Hans Thoma

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 200\, 000)$. 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).

5
1 0 0
1 0 1
3 0 1
3 0 0
3 0 1

0

5
3 1 1
0 3 1
1 3 1
1 2 1
0 4 1

4