/ 
Time Limit: 6 sec / Memory Limit: 2048 MB
配点 : 100 点
After solving the problem Fast as Ryser, you learned how to count the number of matchings in a general graph in O(2^{N/2} N^2). So you decided to write this problem to encourage people to solve the problem and learn new technology.
The time limit and the memory limit of this problem might be very tight. We are sorry for any inconvenience.
問題文
無向グラフ G は 1, 2, \ldots, N を頂点とし，頂点 u と頂点 v を結ぶ辺はちょうど A_{u,v} 本ある (1 \le u, v \le N)．すべての辺は区別される．
各 k = 0, 1, \ldots, \lfloor N/2 \rfloor に対し，G の大きさ k のマッチングの個数を 2^{64} で割った余りを求めよ．
(G の大きさ k のマッチングとは，G の辺 k 本からなる集合であって，それらの端点 2 k 個が相異なるようなものを指す．)
制約
- 1 \le N \le 40．
- 0 \le A_{u,v} < 2^{64} (1 \le u, v \le N)．
- A_{u,u} = 0 (1 \le u \le N)．
- A_{u,v} = A_{v,u} (1 \le u, v \le N)．
入力
入力は以下の形式で標準入力から与えられる．
N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
出力
G の大きさ k のマッチングの個数を 2^{64} で割った余りを b_k として (0 \le k \le \lfloor N/2 \rfloor)，以下の形式で出力せよ．
b_0 b_1 \cdots b_{\lfloor N/2 \rfloor}
入力例 1
4 0 10 300 0 10 0 5 400 300 5 0 20 0 400 20 0
出力例 1
1 735 120200
G の大きさ 2 のマッチングは，以下の通りである．
- 頂点 1, 2 を結ぶ辺のうち 1 本と，頂点 3, 4 を結ぶ辺のうち 1 本からなるものが 200 個
- 頂点 1, 3 を結ぶ辺のうち 1 本と，頂点 2, 4 を結ぶ辺のうち 1 本からなるものが 120\,000 個
入力例 2
7 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
出力例 2
1 21 105 105
入力例 3
10 0 8629318490492529455 16934461172002342162 16689922355946803515 6532726440738276996 1194408499640297875 15866676155001669889 6498797546467110859 16876940315014902410 12387509481131737340 8629318490492529455 0 11507224725899007093 8715646015311805917 10082055328422634515 11661112510609506937 5671467989936109679 9958089075065687029 1044511129638713462 9641449008999128869 16934461172002342162 11507224725899007093 0 9017212196119468141 8742031656924741889 16712732165713258491 12486619021854068086 8079880079267306335 7411259632269635598 847494329973810398 16689922355946803515 8715646015311805917 9017212196119468141 0 16283252096557152371 8615030617835929416 17667878928797645683 18446439882335127774 11475081586957078864 15537196317840490094 6532726440738276996 10082055328422634515 8742031656924741889 16283252096557152371 0 2328769271400341339 5743580703459253102 13482125554117518013 8310663885706538154 15657502149293391713 1194408499640297875 11661112510609506937 16712732165713258491 8615030617835929416 2328769271400341339 0 13134573721194912427 3260072811817230082 12647757802949221999 15331084503094140917 15866676155001669889 5671467989936109679 12486619021854068086 17667878928797645683 5743580703459253102 13134573721194912427 0 5011674754910118042 4293452480892783480 12853153721226986708 6498797546467110859 9958089075065687029 8079880079267306335 18446439882335127774 13482125554117518013 3260072811817230082 5011674754910118042 0 8466317684966562639 13151347917827920992 16876940315014902410 1044511129638713462 7411259632269635598 11475081586957078864 8310663885706538154 12647757802949221999 4293452480892783480 8466317684966562639 0 1834230013668150904 12387509481131737340 9641449008999128869 847494329973810398 15537196317840490094 15657502149293391713 15331084503094140917 12853153721226986708 13151347917827920992 1834230013668150904 0
出力例 3
1 13998873960259808869 16134958027077044128 15075909322183550749 13815169532537848652 14625654317779811048