B. Counting Multisets
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$, $$${\rm 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\leq T\leq 100$$$), representing the number of test cases.

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

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

  • the number of test cases with $$${\rm pcnt}(y_{\max}) \gt 5$$$ does not exceed $$$30$$$.
  • the number of test cases with $$${\rm pcnt}(y_{\max}) \gt 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.

Example
Input
2
7 10 7
9 16 7
Output
0 0 1 3 0 2 2 2
0 0 1 0 0 0 0 0