AT_mujin_pc_2018_g 移動

[problemUrl]: https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_g この問題では $ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ e_1 $ $ f_1 $ $ k_1 $ $ : $ $ a_Q $ $ b_Q $ $ c_Q $ $ d_Q $ $ e_Q $ $ f_Q $ $ k_Q $

各クエリに対し、時刻 $ 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 $ でない - 入力はすべて整数である ### Sample Explanation 1 最初のクエリでは、時刻 $ 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 $ 個です。