Counting Multisets
对于一个由非负整数构成的多重集 S,定义 p(S) 为将其中所有元素排列后,能得到的不同序列数量。例如 S={1,1,2} 时,三种序列为 (1,1,2),(1,2,1),(2,1,1),所以 p(S)=3。
定义 f(n,x,y) 为满足以下全部条件的多重集 S 的数量:
- ∣S∣=n,其中重复元素也计入大小;
- 所有元素之和为 x;
- 所有元素按位或的结果为 y;
- p(S) 是奇数。
给定 n,x,ymax,对 ymax 的每个二进制子掩码 y,计算 f(n,x,y),对 109+7 取模。
这里“子掩码”指 y&ymax=y,包含 0 和 ymax 本身;并不是所有数值上不超过 ymax 的整数。元素 0 允许在多重集中出现。
输入格式
第一行一个整数 T(1≤T≤100),表示测试用例数。
接下来 T 行,每行三个整数 n,x,ymax,满足
$$1\le n<2^{30},\qquad0\le x<2^{45},\qquad0\le y_{\max}<2^{15}.$$
设 pcnt(v) 表示 v 的二进制表示中 1 的数量。保证同一个输入文件中:
- pcnt(ymax)>5 的用例至多 30 个;
- pcnt(ymax)>10 的用例至多 4 个。
输出格式
每个测试用例输出一行,按照子掩码 y 的数值从小到大,输出所有 f(n,x,y)。相邻整数以空格分隔。这一行恰有 2pcnt(ymax) 个整数。
样例
输入:
2
7 10 7
9 16 7
输出:
0 0 1 3 0 2 2 2
0 0 1 0 0 0 0 0