For a multiset $S$ consisting of non-negative integers, let $p(S)$ denote the number of distinct sequences obtained by permuting the elements of $S$.

For example, if $S = \{1, 1, 2\}$, then there are three distinct sequences: $\{1, 1, 2\}$, $\{1, 2, 1\}$, and $\{2, 1, 1\}$, so $p(S) = 3$.

For non-negative integers $n, x, y$, let $f(n, x, y)$ be the number of multisets $S$ satisfying the following conditions: $|S| = n$, $\sum_{i \in S} i = x$, $\text{OR}_{i \in S} i = y$, and $p(S)$ is odd.

Now, given non-negative integers $n, x, y_{\max}$, calculate $f(n, x, y)$ for any subset $y$ of the binary representation of $y_{\max}$, modulo $10^9 + 7$.

Input

The first line contains a positive integer $T$ ($1 \le T \le 100$), representing the number of test cases.

For the next $T$ lines, each line contains three non-negative integers $n, x, y_{\max}$ ($1 \le n < 2^{30}$, $0 \le x < 2^{45}$, $0 \le y_{\max} < 2^{15}$), denoting each test case.

Let $\text{pcnt}(x)$ represent the number of 1s in the binary representation of $x$. It is guaranteed that:

• the number of test cases with $\text{pcnt}(y_{\max}) > 5$ does not exceed 30.
• the number of test cases with $\text{pcnt}(y_{\max}) > 10$ does not exceed 4.

Output

For each test case, output one line with several integers. Specifically, for all subsets $y$ of $y_{\max}$ in binary representation, output $f(n, x, y)$ in ascending order of $y$, separated by spaces.

Examples

Input 1

2
7 10 7
9 16 7

Output 1

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