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

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

两人轮流行动，Alice 先手。

Alice 的回合中，她必须执行以下操作之一：

• 吃掉她拥有的一整块巧克力的所有碎片。也就是说，选择某个 $o_i=0$ 的巧克力，将这块巧克力当前的所有碎片全部从游戏中移除；
• 切开当前任意一块巧克力碎片，不要求这块巧克力属于她。如果被切的碎片大小为 $a\times b$，则她可以将其切成 $x\times b$ 和 $(a-x)\times b$ 两块，其中 $x$ 是斐波那契数，且 $0<x<a$。

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

• 吃掉他拥有的一整块巧克力的所有碎片。也就是说，选择某个 $o_i=1$ 的巧克力，将这块巧克力当前的所有碎片全部从游戏中移除；
• 切开当前任意一块巧克力碎片，不要求这块巧克力属于他。如果被切的碎片大小为 $a\times b$，则他可以将其切成 $a\times y$ 和 $a\times(b-y)$ 两块，其中 $y$ 是斐波那契数，且 $0<y<b$。

当当前玩家没有合法操作时游戏结束。无法行动的玩家失败。

一共有 $2^n$ 个子集。两个子集不同，当且仅当存在某个编号 $i$，第 $i$ 块巧克力在一个子集中出现、在另一个子集中不出现。

请计算有多少个非空子集，在双方都采用最优策略时 Alice 获胜。答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $n$：

接下来 $n$ 行，每行包含三个整数 $w_i,h_i,o_i$：

其中 $o_i=0$ 表示第 $i$ 块巧克力属于 Alice，$o_i=1$ 表示属于 Bob。

输出格式

输出一个整数，表示使 Alice 获胜的非空子集数量，对 $998244353$ 取模。

样例

样例 1

2
1 1 0
1 1 1

1

样例 2

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

6