/ 
Time Limit: 4 sec / Memory Limit: 2048 MB
配点 : 100 点
We did not prove that our solutions work for (1 - \varepsilon) of all possible cases within the constraints for reasonably small \varepsilon. Our sincerest apologies. We solemnly affirm that the actual tests have been generated randomly as described in the problem statement, without any intention to favor our solutions. We wish you a Merry Christmas so that you can safely ignore rare cases which might cause trouble in your solution.
問題文
正整数 N および 16 個の整数 W_{i,j} (0 \le i,j \le 3) が与えられる．ここで，W_{0,0}=0 が保証されている．
うさぎが今平面上の座標 (0,0) に立っており，これから以下の操作を好きな回数行う．
- 現在立っている座標を (x,y) とする．整数 i,j (0 \le i,j \le 3) を選び，座標 (x+i,y+j) にジャンプして移動する．このとき，x+i \geq y+j を満たす必要がある．この操作の重みは W_{i,j} である．
操作列の重みを，その中で行った操作の重みの総積と定義する．
各 k=1,2,\ldots,N に対し次の問題を解け．
- うさぎが最終的に座標 (k,k) に至るすべての操作列の重みの和を 998244353 で割った余りを求めよ．
なお，この問題のテストケースについて以下の情報が開示される．
- サンプルを除くすべてのテストケースについて，W_{i,j} の値は制約の範囲内で一様ランダムに選択されている．
- サンプルを除くテストケースの総数は 10 である．
制約
- 2 \le N \le 250\,000．
- 0 \le W_{i,j} < 998244353 (0 \le i,j \le 3)．
- W_{0,0}=0．
入力
入力は以下の形式で標準入力から与えられる．
N
W_{0,0} W_{0,1} W_{0,2} W_{0,3}
W_{1,0} W_{1,1} W_{1,2} W_{1,3}
W_{2,0} W_{2,1} W_{2,2} W_{2,3}
W_{3,0} W_{3,1} W_{3,2} W_{3,3}
出力
各 k=1,2,\ldots,N に対する答えをこの順に空白区切りで出力せよ．
入力例 1
10 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
出力例 1
1 2 5 14 42 132 429 1430 4862 16796
入力例 2
20 0 130171465 825060067 310308502 32807742 472394518 556273189 402133431 18860036 731819479 614014131 516327409 540765157 764797868 805340356 885719657
出力例 2
220800069 663178740 402492745 787371697 340681055 764687638 248275291 239071271 579317784 142439206 202142764 449124008 17082226 208225793 292943419 63532736 780653882 855023292 155627784 988995756