AT_xmascon16_f.Fifty-Fifty?

兔子有 $A$ 个 A 和 $B$ 个 B。兔子想知道，从这些字母中选出 $N$ 个并排列后，可以构成多少个 $K$ 次回文，并且关心这个数量的奇偶性。

这里，$K$ 次回文指的是，通过恰好进行 $K$ 次如下操作之一，可以将字符串变为回文的字符串：

• 添加：在字符串末尾添加一个字母。
• 删除：删除字符串末尾的一个字母。
• 替换：将字符串末尾的一个字母替换为另一个字母。

例如，ABB 通过一次添加操作可以变为 ABBA，因此是 $1$ 次回文。同时，先删除一次再替换一次可以变为 AA，因此也是 $2$ 次回文。

本题包含多个测试用例。测试用例的数量为 $T$，第 $i$ 个测试用例给出 $N_i,\ A_i,\ B_i,\ K_i$。

输入以如下格式从标准输入读入：

$T$ $N_1$ $A_1$ $B_1$ $K_1$ $N_2$ $A_2$ $B_2$ $K_2$ $\cdots$ $N_T$ $A_T$ $B_T$ $K_T$

对于每个测试用例，输出能够构成的 $K$ 次回文的个数对 $2$ 取余的结果，每行输出一个。

限制条件

• $1 \leq T \leq 100$。
• $0 \leq A_i, B_i \leq 100$。
• $1 \leq N_i \leq A_i+B_i$。
• $0 \leq K_i \leq N_i$。

样例解释 1

第 $1$ 个测试用例中，能够构成的 $0$ 次回文有 AAA 和 ABA 共 $2$ 个。注意，$0$ 次回文即为本身就是回文的字符串。第 $2$ 个测试用例中，能够构成的 $2$ 次回文有 ABB、BAB 和 BBA 共 $3$ 个。

由 ChatGPT 4.1 翻译