对于一个由非负整数组成的多重集 $S$，令 $p(S)$ 表示通过排列 $S$ 中的元素所能得到的不同序列的数量。 例如，若 $S = \{1, 1, 2\}$，则有三个不同的序列：$\{1, 1, 2\}$、$\{1, 2, 1\}$ 和 $\{2, 1, 1\}$，因此 $p(S) = 3$。

对于非负整数 $n, x, y$，令 $f(n, x, y)$ 为满足以下条件的多重集 $S$ 的数量：$|S| = n$，$\sum_{i \in S} i = x$，$\text{OR}_{i \in S} i = y$，且 $p(S)$ 为奇数。

现在，给定非负整数 $n, x, y_{\max}$，计算对于 $y_{\max}$ 二进制表示的任意子集 $y$，对应的 $f(n, x, y)$，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 接下来的 $T$ 行，每行包含三个非负整数 $n, x, y_{\max}$ ($1 \le n < 2^{30}, 0 \le x < 2^{45}, 0 \le y_{\max} < 2^{15}$)，表示每个测试用例。

令 $\text{pcnt}(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数。保证： $\text{pcnt}(y_{\max}) > 5$ 的测试用例数量不超过 $30$。 $\text{pcnt}(y_{\max}) > 10$ 的测试用例数量不超过 $4$。

输出格式

对于每个测试用例，输出一行包含若干整数。具体而言，对于 $y_{\max}$ 二进制表示的所有子集 $y$，按 $y$ 的升序输出 $f(n, x, y)$，并用空格分隔。

样例

样例输入 1

2
7 10 7
9 16 7

样例输出 1

0 0 1 3 0 2 2 2
0 0 1 0 0 0 0 0