整数 \(N\) と、各要素が \(0\) または \(1\) である \(N\) 行 \(N\) 列の行列 \(A\) が与えられます。\(A\) の \(i\) 行 \(j\) 列の要素を \(A_{i,j}\) と表します。
\((1,2,\dots,N)\) を並べ替えて得られる順列 \(P=(P_1,P_2,\dots,P_N)\) であって、以下の条件を満たすものの個数を \(998244353\) で割ったあまりを求めてください。
ただし、\(X \,\&\, Y\) は \(X\) と \(Y\) のビットごとの論理積 (bitwise AND) を表します。
入力は以下の形式で標準入力から与えられます。
| \(N\) | |
| \(A_{1,1}~A_{1,2}~\dots~A_{1,N}\) | |
| \(A_{2,1}~A_{2,2}~\dots~A_{2,N}\) | |
| \(\vdots\) | |
| \(A_{N,1}~A_{N,2}~\dots~A_{N,N}\) |
制約は以下の通りです。
条件を満たす順列 \(P\) の個数を \(998244353\) で割ったあまりを \(1\) 行に出力してください。
31 0 01 1 01 0 1
2
21 10 1
0
51 0 0 0 00 1 0 0 01 1 1 0 00 1 0 1 01 0 0 0 1
2
サンプル \(1\) について:
条件を満たす順列は \(P=(3,1,2)\) と \(P=(3,2,1)\) の \(2\) つです。例えば \(P=(3,1,2)\) のとき、\(P_2 \,\&\, P_1 = 1 \,\&\, 3 = 1 = P_2\) なので \(A_{2,1}=1\) である必要がありますが、実際に \(A_{2,1}=1\) となっています。他のすべての \((i,j)\) についても条件が成り立つことが確かめられます。
サンプル \(2\) について:
\(1 \,\&\, 2 = 0\) なので、どの順列でも \(P_1 \,\&\, P_2 \neq P_1\) となり、\(A_{1,2}=0\) でなければなりません。しかし \(A_{1,2}=1\) なので、条件を満たす順列は存在せず、答えは \(0\) です。
サンプル \(3\) について:
条件を満たす順列は \(P=(5,3,1,2,4)\) と \(P=(3,5,1,4,2)\) の \(2\) つです。