問題文
素数 P が与えられます。また、N 次正方行列 A が次のように与えられます。
A=A1,1A2,1⋮AN,1A1,2A2,2⋮AN,2⋯⋯⋱⋯A1,NA2,N⋮AN,N
各 Ai,j (1≤i,j≤N) は −1 もしくは 0 以上 P 未満の整数です。
行列 A に含まれる −1 のそれぞれを 0 以上 P 未満の整数に変えることで得られる A は、A に含まれる −1 の数を M 個として PM 個あります。
それら全てに対して A の行列式 detA を求め、その総和を P で割ったあまり(0 以上 P 未満)を答えてください。
detA を P で割ったあまりの総和を答えるのではないことに注意してください。
T 個の独立なテストケースについて答えを求めてください。
注記
行列式とは? (クリックして展開)
N を正整数とします。(1,2,⋯,N) の順列 σ=(σ1,σ2,⋯,σN) に対して、 σ の転倒数を 1≤i<j≤N を満たす整数の組 (i,j) であって σi>σj を満たすものの個数とします。
SN を (1,2,⋯,N) の順列全体の集合とし、σ∈SN に対して順列の符号 sgn σ を、σ の転倒数が偶数なら sgn σ=1、奇数なら sgn σ=−1 と定めます。
このとき、実数からなる N 次正方行列 A=(Ai,j) に対して、その行列式 detA を次のように定義します。
detA=σ∈SN∑{(sgn σ)i=1∏NAi,σi}
ここで、P∈SN∑ とは (1,2,⋯,N) の順列 σ すべてについての和、i=1∏Nxi は x1×x2×⋯×xN を表します。なお、今回はこのように行列式を定義しておりますが、一般的ではない説明になっているかもしれません。ただし、この定義は他の行列式の定義と同値です。
(1324) の行列式 detA は、sgn((1,2))=1,sgn((2,1))=−1 なので detA=1×4−2×3=−2 となります。
N=3 の場合、B=112131122232132333 の行列式 detB は、detB=11×22×33−11×23×32−12×21×33+12×23×31+13×21×32−13×22×31=0 となります。
入力
入力は以下の形式で標準入力から与えられます。ここで、
testi は
i 番目のテストケースを表します。
T
test1
test2
⋮
testT
各テストケースは以下の形式で与えられます。
N P
A1,1A2,1⋮AN,1A1,2A2,2⋮AN,2⋯⋯⋱⋯A1,NA2,N⋮AN,N
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。