非負整数からなる多重集合 $S$ に対して、$p(S)$ を $S$ の要素を並べ替えて得られる異なる数列の個数とする。

例えば、$S = \{1, 1, 2\}$ の場合、異なる数列は $\{1, 1, 2\}, \{1, 2, 1\}, \{2, 1, 1\}$ の3通りであり、$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$ 行の各行には、3つの非負整数 $n, x, y_{\max}$ ($1 \le n < 2^{30}, 0 \le x < 2^{45}, 0 \le y_{\max} < 2^{15}$) が含まれる。

$x$ の二進表現における $1$ の個数を $\text{pcnt}(x)$ とする。以下のことが保証されている：

• $\text{pcnt}(y_{\max}) > 5$ となるテストケースの数は $30$ を超えない。
• $\text{pcnt}(y_{\max}) > 10$ となるテストケースの数は $4$ を超えない。

出力

各テストケースについて、複数の整数を1行で出力せよ。具体的には、$y_{\max}$ の二進表現のすべての部分集合 $y$ に対して、$f(n, x, y)$ を $y$ の昇順にスペース区切りで出力せよ。

入出力例

入出力例 1

2
7 10 7
9 16 7

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