Count the number of integer sequence a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an satisfying the following conditions, modulo 998244353998\,244\,353998244353:
∀i∈Z∩[1,n]\forall i \in \mathbb{Z} \cap [1,n]∀i∈Z∩[1,n], ∃S⊆Z∩[1,m]\exists S \subseteq \mathbb{Z} \cap [1,m]∃S⊆Z∩[1,m], ai=⨁j∈Sbi,ja_i = \bigoplus_{j \in S} b_{i,j}ai=⨁j∈Sbi,j. That is, aia_iai is equal to the bitwise XOR sum of some subsequence of (bi,1,bi,2,…,bi,m)(b_{i,1},b_{i,2},\ldots,b_{i,m})(bi,1,bi,2,…,bi,m), and ai=0a_i = 0ai=0 if the subsequence is empty.
The number of i∈Z∩[2,n]i \in \mathbb{Z} \cap [2,n]i∈Z∩[2,n] that ai−1≠aia_{i-1} \neq a_{i}ai−1=ai is minimized among all the sequences satisfying the above two conditions.
输入格式
The first line contains four integers n,m,l,rn,m,l,rn,m,l,r (2≤n≤1052 \le n \le 10^52≤n≤105, 2≤nm2≤4×1072 \le nm^2 \le 4 \times 10^72≤nm2≤4×107, 0≤l≤r<2m0 \le l \le r < 2^m0≤l≤r<2m).
The iii-th of the following nnn lines contains mmm integers bi,1,bi,2,…,bi,mb_{i,1},b_{i,2},\ldots,b_{i,m}bi,1,bi,2,…,bi,m (0≤bi,j<2m0 \le b_{i,j} < 2^m0≤bi,j<2m).
Please note that l,r,bi,jl,r,b_{i,j}l,r,bi,j are given in binary notation length of mmm.