Description

There are $n$ chocolates. The $i$-th chocolate has size $w_i \times h_i$ and belongs either to Alice or to Bob. Chocolates cannot be rotated by $90^{\circ}$ during the game, that is, chocolates of sizes $a \times b$ and $b \times a$ are considered different.

A non-empty subset of these chocolates is chosen; the remaining chocolates are discarded. A game between Alice and Bob is then played using the chosen chocolates.

The players take turns making moves, starting with Alice. On her turn, Alice can do exactly one of the following:

• eat all pieces of one of her chocolates (that is, for some $i$ such that $o_i = 0$, all pieces of this chocolate, whose total area is $w_i \times h_i$---possibly including pieces obtained earlier by splitting by either player---are removed from the game);
• split one of the current pieces of any chocolate, not necessarily her own. If the piece being split has size $a \times b$, then it can be split into two pieces of sizes $x \times b$ and $(a - x) \times b$, where $x$ is a Fibonacci number such that $0 < x < a$.

On his turn, Bob can do exactly one of the following:

• eat all pieces of one of his chocolates (that is, for some $i$ such that $o_i = 1$, all pieces of this chocolate, whose total area is $w_i \times h_i$---possibly including pieces obtained earlier by splitting by either player---are removed from the game);
• split one of the current pieces of any chocolate, not necessarily his own. If the piece being split has size $a \times b$, then it can be split into two pieces of sizes $a \times y$ and $a \times (b - y)$, where $y$ is a Fibonacci number such that $0 < y < b$.

The game ends when the current player has no valid moves. The player who cannot make a move loses the game.

Subsets are chosen among the $2^n$ possible subsets. Two subsets are considered different if there exists an index $i \in \{1, \ldots, n\}$ such that the $i$-th chocolate is present in one subset but absent in the other.

Your task is to compute the number of non-empty subsets of chocolates for which Alice wins, assuming both players play optimally. Output the result modulo $998\,244\,353$.

Input Format

The first line contains a single integer $n$ ($1 \leq n \leq 100$): the number of chocolates.

The next $n$ lines each contain three integers: $w_i$, $h_i$ ($1 \leq w_i, h_i \leq 50$), and $o_i \in \{0, 1\}$ --- the width and height of the $i$-th chocolate, and its owner. $o_i = 0$ if the $i$-th chocolate belongs to Alice, $o_i = 1$ if it belongs to Bob.

Output Format

Print one integer: the number of non-empty subsets of the chocolates such that Alice wins the game on that subset, modulo $998\,244\,353$.

2
1 1 0
1 1 1

1

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

6