問題文

この問題では Q 個のクエリが与えられます。i 個目のクエリは 7 つの整数 a_i,b_i,c_i,d_i,e_i,f_i,k_i で表されます。 クエリ毎に、x_1=a_i,y_1=b_i,x_2=c_i,y_2=d_i,x_3=e_i,y_3=f_i,K=k_i として以下の問題を解いた答えを出力してください。

ロボットが 1 台あり、時刻 0 には xy 平面上の点 (0,0) にいます。 ロボットはいずれも (0,0) でなくどの 2 つの向きも全く同じでも正反対でもない 3 つのベクトル (x_1,y_1),(x_2,y_2),(x_3,y_3) を持っており、以下の規則で移動します。

• 時刻 t にロボットがいる座標を (x,y) とすれば、時刻 t+1 には、ロボットは座標 (x,y),(x+x_1,y+y_1),(x+x_2,y+y_2),(x+x_3,y+y_3) のいずれかにいる。

非負整数 K が与えられます。時刻 K にロボットがいる点としてありうるものの個数を 998244353 で割ったあまりを求めてください。

制約

• 1 \leq Q \leq 10^4
• 0 \leq |a_i|,|b_i|,|c_i|,|d_i|,|e_i|,|f_i| \leq 10^9
• 0 \leq k_i \leq 10^9
• 各 i に対し、(a_i,b_i),(c_i,d_i),(e_i,f_i) はいずれも (0,0) でなく、かつこれらのうちのどの 2 つも同じ向きを向いておらず、どの 2 つも全く正反対の向きを向いていない。より正確には、どの 2 つの外積も 0 でない
• 入力はすべて整数である

入力例 1

9
1 0 0 1 1 1 3
1 0 0 1 -1 -1 3
3 1 4 1 5 9 265
77162 -78112 -90809 -88927 99617 -89012 1000000000
123 456 789 -123 -456 -789 987654321
0 1 2 3 4 5 0
10000000 10000000 20000000 30000000 -50000000 -80000000 130000000
123456789 442514372 -902777152 -78816277 -887267123 667261667 908855261
1 2 3 4 5 6 7

出力例 1

16
19
981646
677426955
667519055
1
233035917
508252191
64

最初のクエリでは、時刻 3 にロボットがいる点としてありうるものは (x,y)(0\leq x,y\leq 3) とあらわされる点であり、これは 16 個あります。 2 番目のクエリでは、時刻 3 にロボットがいる点としてありうるものは (-3,-3),(-2,-2),(-2,-1),(-1,-2),(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(0,2),(0,3),(1,-1),(1,0),(1,1),(1,2),(2,0),(2,1),(3,0) の 19 個です。