AT_ndpc2026_r 3 つ組

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 $ .

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 $

Print the number of good sequences that are subsequences of $ A $ with length at least $ 2 $ , modulo $ 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 Explanation 1 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