AT_iroha2019_day1_j ヌクレオチド

高桥君为了实现他的世界征服计划，决定制造 $ Q $ 种病毒。为此，他需要设计一些碱基序列，但候选方案实在太多，因此向你寻求帮助。 他希望第 $ x $ 种病毒的碱基序列能够通过一个长度为 $ N_x $ 的数列 $ A_1, A_2, \cdots, A_{N_x} $ 来描述，同时需要满足以下条件： - 数列的每个元素只能是 $ 0 $ 或 $ 1 $。 - 数列是回文数列，即对于所有 $ 1 \leq i \leq N_x $，有 $ A_i = A_{N_x + 1 - i} $。 - 数列的逆序对数恰好是 $ K_x $。逆序对数是指数列中所有满足 $ i < j $ 且 $ A_i > A_j $ 的整数对 $(i, j)$ 的数量。 我们需要计算，满足上述条件的数列 $ A $ 一共有多少种可能。由于这个数量可能非常大，请输出结果对 $ 10^9 + 7 $ 取模后的值。

输入通过标准输入给出，格式如下： > $ Q $ > $ N_1\ K_1 $ > $\vdots$ > $ N_Q\ K_Q $

请输出 $ Q $ 行。第 $ i $ 行表示第 $ i $ 种病毒的碱基序列满足条件的数列数量，并输出对 $ 10^9 + 7 $ 取模的结果。

- $ 1 \leq Q \leq 10^5 $ - $ 1 \leq N_i \leq 10^5 $ - $ 0 \leq K_i \leq \frac{N_i (N_i - 1)}{2} $ - 所有输入都是整数。 **本翻译由 AI 自动生成**