#P18174. Counting Multisets

Counting Multisets

Counting Multisets

对于一个由非负整数构成的多重集 SS,定义 p(S)p(S) 为将其中所有元素排列后,能得到的不同序列数量。例如 S={1,1,2}S=\{1,1,2\} 时,三种序列为 (1,1,2),(1,2,1),(2,1,1)(1,1,2),(1,2,1),(2,1,1),所以 p(S)=3p(S)=3。

定义 f(n,x,y)f(n,x,y) 为满足以下全部条件的多重集 SS 的数量:

  • ∣S∣=n|S|=n,其中重复元素也计入大小;
  • 所有元素之和为 xx;
  • 所有元素按位或的结果为 yy;
  • p(S)p(S) 是奇数。

给定 n,x,ymax⁡n,x,y_{\max},对 ymax⁡y_{\max} 的每个二进制子掩码 yy,计算 f(n,x,y)f(n,x,y),对 109+710^9+7 取模。

这里“子掩码”指 y&ymax⁡=yy\mathbin{\&}y_{\max}=y,包含 0 和 ymax⁡y_{\max} 本身;并不是所有数值上不超过 ymax⁡y_{\max} 的整数。元素 0 允许在多重集中出现。

输入格式

第一行一个整数 TT(1≤T≤1001\le T\le100),表示测试用例数。

接下来 TT 行,每行三个整数 n,x,ymax⁡n,x,y_{\max},满足

$$1\le n<2^{30},\qquad0\le x<2^{45},\qquad0\le y_{\max}<2^{15}.$$

设 pcnt⁡(v)\operatorname{pcnt}(v) 表示 vv 的二进制表示中 1 的数量。保证同一个输入文件中:

  • pcnt⁡(ymax⁡)>5\operatorname{pcnt}(y_{\max})>5 的用例至多 30 个;
  • pcnt⁡(ymax⁡)>10\operatorname{pcnt}(y_{\max})>10 的用例至多 4 个。

输出格式

每个测试用例输出一行,按照子掩码 yy 的数值从小到大,输出所有 f(n,x,y)f(n,x,y)。相邻整数以空格分隔。这一行恰有 2pcnt⁡(ymax⁡)2^{\operatorname{pcnt}(y_{\max})} 个整数。

样例

输入:

2
7 10 7
9 16 7

输出:

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