AT_KeioPC2025_d Can I Press Them All?

$ M $ 次元空間上の点が $ N $ 個与えられます。 $ i $ 個目の点は $ (x_{i,1},x_{i,2},\dots,x_{i,M}) $ にあります。また、非負整数 $ D $ も与えられます。 $ \lbrace 1,2,\dots,N \rbrace $ の部分集合の組 $ (S_1,S_2) $ のうち、以下の条件を全て満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ 1 \le i \le N $ を満たす整数 $ i $ は $ S_1,S_2 $ のうち片方にのみ含まれる。 - $ a,b \in S_c $ を満たす任意の $ a,b,c $ に対して、 $ \sum_{i=1}^{M} |x_{a,i} - x_{b,i}| \le D $ を満たす。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ D $ $ x_{1,1}\ x_{1,2}\ \dots\ x_{1,M} $ $ x_{2,1}\ x_{2,2}\ \dots\ x_{2,M} $ $ \vdots $ $ x_{N,1}\ x_{N,2}\ \dots\ x_{N,M} $

$ T $ 行出力せよ。 $ i $ 行目には $ \mathrm{case}_i $ の答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについては、 $ (S_1,S_2) = (\lbrace 1,2 \rbrace,\lbrace 3,4 \rbrace),(\lbrace 3,4 \rbrace,\lbrace 1,2 \rbrace) $ の $ 2 $ 個が条件を満たします。 $ 2 $ 番目のテストケースについては、条件を満たす $ (S_1,S_2) $ は存在しません。 ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le M \le 4 $ - $ 0 \le D \le 10^9 $ - $ 0 \le x_{i,j} \le 10^9 $ - すべてのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力はすべて整数