有 $n$ 块巧克力。第 $i$ 块巧克力的大小为 $w_i \times h_i$，且属于 Alice 或 Bob。在游戏过程中，巧克力不能旋转 $90^\circ$，也就是说，大小为 $a \times b$ 和 $b \times a$ 的巧克力被视为不同的巧克力。

选择这些巧克力的一个非空子集，其余的巧克力被丢弃。然后，Alice 和 Bob 使用选中的巧克力进行游戏。

玩家轮流进行操作，由 Alice 先手。在她的回合中，Alice 可以执行以下操作之一：

• 吃掉属于她的某块巧克力的所有碎片（即对于某个满足 $o_i = 0$ 的 $i$，将该巧克力的所有碎片从游戏中移除，其总面积为 $w_i \times h_i$——可能包括之前由任意玩家切分得到的碎片）；
• 切分当前任意一块巧克力（不一定属于她自己）的其中一个碎片。如果被切分的碎片大小为 $a \times b$，则可以将其切分为大小为 $x \times b$ 和 $(a - x) \times b$ 的两块，其中 $x$ 是一个斐波那契数，且满足 $0 < x < a$。

在 Bob 的回合中，他可以执行以下操作之一：

• 吃掉属于他的某块巧克力的所有碎片（即对于某个满足 $o_i = 1$ 的 $i$，将该巧克力的所有碎片从游戏中移除，其总面积为 $w_i \times h_i$——可能包括之前由任意玩家切分得到的碎片）；
• 切分当前任意一块巧克力（不一定属于他自己）的其中一个碎片。如果被切分的碎片大小为 $a \times b$，则可以将其切分为大小为 $a \times y$ 和 $a \times (b - y)$ 的两块，其中 $y$ 是一个斐波那契数，且满足 $0 < y < b$。

当当前玩家没有合法操作时，游戏结束。无法进行操作的玩家输掉游戏。

在 $2^n$ 个可能的子集中选择子集。如果存在一个索引 $i \in \{1, \dots, n\}$ 使得第 $i$ 块巧克力在其中一个子集中出现但在另一个子集中未出现，则认为这两个子集是不同的。

你的任务是计算在双方都采取最优策略的情况下，Alice 获胜的非空巧克力子集的数量。输出结果模 $998\,244\,353$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100$)：巧克力的数量。

接下来的 $n$ 行，每行包含三个整数：$w_i$，$h_i$ ($1 \le w_i, h_i \le 50$) 和 $o_i \in \{0, 1\}$ —— 第 $i$ 块巧克力的宽度、高度以及所有者。如果第 $i$ 块巧克力属于 Alice，则 $o_i = 0$；如果属于 Bob，则 $o_i = 1$。

输出格式

输出一个整数：在选出的子集上 Alice 获胜的非空巧克力子集数量，模 $998\,244\,353$。

样例

输入样例 1

2
1 1 0
1 1 1

输出样例 1

1

输入样例 2

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

输出样例 2

6