We call a matrix "01 Square" if and only if it's a N×NNtimes NN×N matrix and its elements are all 000 or 111. For two 01 Squares XXX,YYY, we define two operators X×YXtimes YX×Y and X⊙YXodot YX⊙Y. The
We call a matrix "01 Square" if and only if it's a N×NNtimes NN×N matrix and its elements are all 000 or 111. For two 01 Squares XXX,YYY, we define two operators X×YXtimes YX×Y and X⊙YXodot YX⊙Y. The value of them are also 01 Square matrices and calculated below(we use ZZZ to abbreviate X×YXtimes YX×Y and DDD to abbreviate X⊙YXodot YX⊙Y): Zi,j=(∑k=1NXi,kYk,j) mod 2Z_{i,j}=(sum_{k=1}^{N}X_{i,k}Y_{k,j})~mod~2Zi,j=(∑k=1NXi,kYk,j) mod 2 Di,j=Xi,jYi,jD_{i,j}=X_{i,j}Y_{i,j}Di,j=Xi,jYi,j Now MianKing has two 01 Squares A,BA,BA,B, he wants to solve the matrix equation below: A×C=B⊙CAtimes C=Bodot CA×C=B⊙C You need to help MainKing solve this problem by calculating how many 01 Squares CCC satisfy this equation. The answer may be very large, so you only need to output the answer module 998244353998244353998244353.
