AT_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 $。我们需要解决如下问题并输出结果。

有一台机器人，初始时刻 $ t=0 $ 处于平面坐标点 $ (0,0) $。机器人可以使用三个向量 $ (x_1, y_1), (x_2, y_2), (x_3, y_3) $ 进行移动。这些向量不为 $ (0,0) $ 并且任意两个向量都不平行或反向。对于每个时刻 $ 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 $ 时，机器人可能在的不同点的个数是多少？请将这个结果 mod $ 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) $ 都不为零向量，并且任意两个向量之间既不平行也不反方向，具体来说，任何两个向量的外积都不为零。
• 所有输入数据均为整数。

样例解释

在第一个查询中，时刻 $ 3 $ 时机器人可以位于满足 $ (x, y) \ (0 \leq x, y \leq 3) $ 的共 $ 16 $ 个不同点。在第二个查询中，可能的位置共有 $ 19 $ 个，具体为：$ (-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) $。

本翻译由 AI 自动生成