AT_ndpc2026_r.Triples

For non-negative integers $u, v$, we write $u \subseteq v$ to mean $u\ \mathrm{OR}\ v = v$. Here, $\mathrm{OR}$ denotes the bitwise OR operation.

A sequence of triples of non-negative integers $((u_1,v_1,w_1),(u_2,v_2,w_2),\dots,(u_k,v_k,w_k))$ is called a good sequence if it satisfies all of the following conditions:

• $k \geq 2$.
• For all integers $i$ such that $1 \leq i \leq k-1$, it holds that $u_i \subseteq w_{i+1} \subseteq v_i$.

You are given a sequence of triples $A = ((x_1,y_1,z_1), (x_2,y_2,z_2), \dots, (x_N,y_N,z_N))$.
For all $i$ such that $1 \leq i \leq N$, it holds that $x_i \subseteq y_i$.

There are $2^N - N - 1$ subsequences of $A$ with length at least $2$ (counting different choices of indices separately).
Among them, find the number of good sequences, modulo $998244353$.

对于非负整数 $u, v$，我们用记号 $u \subseteq v$ 表示 $u\ \mathrm{OR}\ v = v$，其中 $\mathrm{OR}$ 表示按位或运算。

一个由非负整数三元组构成的序列 $((u_1,v_1,w_1),(u_2,v_2,w_2),\dots,(u_k,v_k,w_k))$ 称为好序列，当且仅当它满足以下所有条件：

• $k \geq 2$；
• 对所有满足 $1 \leq i \leq k-1$ 的整数 $i$，均有 $u_i \subseteq w_{i+1} \subseteq v_i$。

给定一个三元组序列 $A = ((x_1,y_1,z_1), (x_2,y_2,z_2), \dots, (x_N,y_N,z_N))$。
对所有满足 $1 \leq i \leq N$ 的 $i$，均有 $x_i \subseteq y_i$。

序列 $A$ 共有 $2^N - N - 1$ 个长度至少为 $2$ 的子序列（按索引的不同选择分别计数）。
在这些子序列中，求好序列的个数，并对 $998244353$ 取模。

The input is given from standard input in the following format:

$N$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_N$ $y_N$ $z_N$

输入从标准输入中按以下格式给出：

$N$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_N$ $y_N$ $z_N$

Print the number of good sequences that are subsequences of $A$ with length at least $2$, modulo $998244353$.

输出 $A$ 的长度至少为 $2$ 的“好序列”子序列的个数，对 $998244353$ 取模。

Partial Score

This problem has partial scoring.

• If you solve the dataset where $\max(x_i, y_i, z_i) < 2^{18}$ holds for every integer $i$ such that $1 \leq i \leq N$, you will get $4$ points.

Sample 1 Explanation:
There are $2$ sequences that satisfy the condition:

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

Constraints

• $2 \leq N \leq 3 \times 10^5$
• $0 \leq x_i < 2^{24}$
• $0 \leq y_i < 2^{24}$
• $0 \leq z_i < 2^{24}$
• $x_i \ \mathrm{OR}\ y_i = y_i$
• All input values are integers

部分得分

本题采用部分得分制。

• 若你解决了满足对每个整数 $i$（其中 $1 \leq i \leq N$）均有 $\max(x_i, y_i, z_i) < 2^{18}$ 的数据集，则可获得 $4$ 分。

样例 1 解释：
共有 $2$ 个序列满足条件：

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

约束条件

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