说明

有 $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, \ldots, n\}$，使得第 $i$ 块巧克力在一个子集中存在而在另一个子集中不存在，则认为这两个子集是不同的。

你的任务是计算使得 Alice 获胜（假设双方均采取最优策略）的非空巧克力子集的数量。输出结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$ （$1 \leq n \leq 100$）：巧克力的数量。

接下来的 $n$ 行每行包含三个整数： $w_i$， $h_i$ （$1 \leq w_i, h_i \leq 50$），以及 $o_i \in \{0, 1\}$ —— 第 $i$ 块巧克力的宽度、高度及其所有者。 $o_i = 0$ 表示第 $i$ 块巧克力属于 Alice， $o_i = 1$ 表示属于 Bob。

输出格式

输出一个整数：使得 Alice 在该子集上的游戏中获胜的非空子集的数量，对 $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

提示

翻译由 DeepSeek 完成