题目描述

对于非负整数 $u,v$，记

$$u\subseteq v$$

表示

$$u\mathbin{\mathrm{OR}}v=v,$$

其中 $\mathrm{OR}$ 表示按位或。

若一个非负整数三元组序列

$$((u_1,v_1,w_1),(u_2,v_2,w_2),\ldots,(u_k,v_k,w_k))$$

满足以下条件，则称其为好序列：

• $k\ge 2$；
• 对每个 $1\le i\le k-1$，都有$$u_i\subseteq w_{i+1}\subseteq v_i.$$

给定三元组序列

$$A=((x_1,y_1,z_1),(x_2,y_2,z_2),\ldots,(x_N,y_N,z_N)),$$

并保证对每个 $i$ 都有 $x_i\subseteq y_i$。

从 $A$ 中按原顺序选取至少两个位置可以得到 $2^N-N-1$ 个非空的长度至少为 $2$ 的子序列；选取位置不同的子序列视为不同。求其中好序列的数量，对 $998244353$ 取模。

限制条件

• $2\le N\le 3\times 10^5$
• $0\le x_i,y_i,z_i<2^{24}$
• $x_i\mathbin{\mathrm{OR}}y_i=y_i$
• 所有输入均为整数。

部分分

• 对所有 $i$ 都满足 $\max(x_i,y_i,z_i)<2^{18}$ 的数据求解正确，可获得 $4$ 分。

输入

N
x_1 y_1 z_1
x_2 y_2 z_2
...
x_N y_N z_N

输出

输出 $A$ 的长度至少为 $2$ 的子序列中，好序列的数量对 $998244353$ 取模后的结果。

样例输入 1

3
2 6 3
0 7 4
1 5 2

样例输出 1

2

满足条件的序列为：

• $((2,6,3),(1,5,2))$
• $((0,7,4),(1,5,2))$

样例输入 2

8
0 9 5
0 16 3
0 8 4
0 5 23
0 20 29
0 12 26
0 6 0
0 19 8

样例输出 2

9

样例输入 3

13
0 16777215 14827221
8390656 12582911 5535137
4325888 16711679 2641072
8849409 16776703 15212885
8389632 16514814 9612654
0 12517373 13419138
0 16777215 5271292
14464 16236535 6997452
131072 15727483 10218943
16 16646111 15524257
1181961 14647295 5595336
8388768 16775147 5472548
0 16777215 297940

样例输出 3

34