题目描述

小 Z 和小 Y 今天学了象棋。

棋盘上有三种棋子：

• 车：走直线；
• 马：走日；
• 象：飞田。

• 车（如（$1$）所示）：车可以移动到棋盘中同一行或同一列的任意位置。移动向量为 $[x, 0]$ 或 $[0, y]$，其中 $x, y$ 为非零整数，并且不能越出棋盘边界。
• 马（如（$2$）所示）：马可以走“日”字，移动到图示的八个位置。移动向量为 $[2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1]$，并且不能越出棋盘边界。
• 象（如（$3$）所示）：象可以走“田”字，移动到图示的四个位置。移动向量为 $[2, 2], [2, -2], [-2, 2], [-2, -2]$，并且不能越出棋盘边界。

小 Y 提出了 $m$ 个问题。第 $i$ 个问题为：

• 棋盘大小为 $a_i \times b_i$；
• 棋盘上只有一个棋子（车/马/象）位于 $(c_i, d_i)$；
• 经过 $e_i$ 步，该棋子可以形成多少种不同路径？

具体地，我们记录棋子 $e_i$ 步移动经过的 $e_i + 1$ 个坐标点作为路径序列。 路径不同当且仅当序列中至少存在一个位置坐标不同。

请计算每个问题的答案，并对 $19260817$ 取模。

输入格式

第一行包含一个整数 $m$，表示问题数量。

接下来 $m$ 行，每行包含六个整数：$op_i, a_i, b_i, c_i, d_i, e_i$

• 若 $op_i = 0$，询问的棋子为车；
• 若 $op_i = 1$，询问的棋子为马；
• 若 $op_i = 2$，询问的棋子为象。

输出格式

共 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个问题的答案（对 $19260817$ 取模）。

样例输入 1

6
0 5 5 1 1 2
1 5 5 1 1 2
2 5 5 1 1 2
0 10 9 4 5 100
1 10 9 4 5 100
2 10 9 4 5 100

样例输出 1

64
12
4
8980677
14680106
12361625

说明

数据范围

对于 $100\%$ 的数据：

• $1 \le m \le 50$，
• $1 \le c_i \le a_i$，
• $1 \le d_i \le b_i$，
• $1 \le a_i \cdot b_i \le 100$，$1 \le e_i \le 10^9$。

对于每个测试点，$a_i \times b_i > 25$ 的数据不超过 $3$ 组。

各测试点的附加限制如下表所示：

点击下载大样例