AT_ndpc2026_r 3 つ組

非負整数 $ u, v $ に対して $ u \subseteq v $ を $ u\ \mathrm{OR}\ v = v $ という意味で用います。ここで $ \mathrm{OR} $ はビットごとの論理和です。 非負整数の $ 3 $ つ組の列 $ ((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 $ が成り立つ。 非負整数の $ 3 $ つ組の列 $ 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 $ 以上の部分列は取り出す位置の違いを区別すると $ 2^N - N - 1 $ 通りありますが、それらの中に含まれる良い列の個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ $ \vdots $ $ x_N $ $ y_N $ $ z_N $

$ A $ の長さ $ 2 $ 以上の部分列である良い列の個数を $ 998244353 $ で割った余りを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ 1 \leq i \leq N $ を満たす整数 $ i $ 全てに対して $ \max(x_i, y_i, z_i) \lt 2^{18} $ が成り立つデータセットに正解した場合、 $ 4 $ 点が与えられる。 ### Sample Explanation 1 条件を満たす列は次の $ 2 $ 通りです。 - $ ((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 \lt 2^{24} $ - $ 0 \leq y_i \lt 2^{24} $ - $ 0 \leq z_i \lt 2^{24} $ - $ x_i \ \mathrm{OR}\ y_i = y_i $ - 入力される値は全て整数