给定 $n,x,y_m$，对于每个 $y<y_m$，求有多少长度为 $n$ 的数组，满足它们加起来是 $x$，或起来是 $y$ 并且这个数组的排列个数是奇数个。

$n<2^{30},x<2^{45},y_m<2^{15}$

数组的排列个数是 $n!/c_i!$，写成组合数就是 $\binom n{n-c_1}\binom{n-c_1-c_2}{c_2}\binom{n-c_1-c_2-c_3}{c_3}\cdots$。
根据 lucas 定理，$n$ 的二进制完全包括 $c_1$，$n-c_1$ 的二进制完全包括 $c_2$……由此，所有 $c_i$ 的二进制与等于 $0$，或等于 $n$。
接下来，相当于把 $1\sim y_m$ 中的每个数分配若干个 $n$ 的二进制 $1$，要求每个数乘以其分配的 $1$ 之和为 $x$。

使用容斥原理，把恰好为 $y$ 转化为至多为 $y$，最后使用高维差分把至多变回恰好。
假如把 $n$ 分成 $2^{a_1},2^{a_2},\cdots$，那么

\[\sum_i 2^{a_i}\times(y的一个子集)=x\]

再次对 $y$ 进行拆位变成 $2^{b_1},2^{b_2},\cdots$，那么对于每个 $a_i,b_j$ 都可以去考虑选不选，其对总和的贡献就是 $2^{a_i+b_j}$。
可以发现，所有贡献都是 $2$ 的整数次幂，因此可以统计出 $a_i+b_j$ 的不同值的数量，然后去 dp。
具体的说，令 $f_{i,j}$ 表示当前值与总和的低 $i$ 位相同，并且 $i$ 位上有之前的值进位后的 $j$，具体实现见代码。

值得注意的是，对于一个 int，其右移超过大于等于 $32$ 是 ub。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define int loli
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=507,P=1e9+7;
struct mint{
	int d;
	mint()=default;
	mint(int x):d(x){}
	friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
	friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
	friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
	mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
	friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
	mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
	friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
	mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
	static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
	friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
	mint&operator/=(mint z){return (*this)*=qpow(z.d);}
	friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
	mint&operator^=(mint z){return *this=qpow(d,z.d);}
	mint operator()(mint z)const{return qpow(d,z.d);}
	mint&operator[](mint z){return *this=qpow(d,z.d);}
	mint inv()const{return qpow(d);}
	mint pow(mint z)const{return qpow(d,z.d);}
	int operator+()const{return d;}
	mint operator-()const{return P-d;}
	int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n,msk,m;
mint g[60][N],fac[N],inv[N];
vector<int>s1,s2;
mint Bi(int x,int y){
	if(x<y)return 0;
	return fac[x]*inv[y]*inv[x-y];
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<N;i++)fac[i]=fac[i-1]*i;
	inv[N-1]=fac[N-1].inv();
	for(int i=N-2;i>=2;i--)inv[i]=inv[i+1]*(i+1);
	int T;cin>>T;while(T--){
		cin>>n>>msk>>m;
		s1.clear();s2.clear();
		for(int i=0;i<=30;i++)if(n>>i&1)s1.push_back(i);
		for(int i=0;i<=15;i++)if(m>>i&1)s2.push_back(i);
		m=siz(s2);
		vector<mint>f(1<<m);
		for(int i=0;i<(1<<m);i++){
			int cnt[60]={},num=0;
			for(int j=0;j<m;j++)if(i>>j&1)
				for(int x:s1)cnt[x+s2[j]]++,num++;
			g[0][0]=1;
			for(int i=0;i<=45;i++)for(int j=0;j<=num/2;j++)if(g[i][j].d){
				for(int k=0;k<=cnt[i];k++)if((j+k)%2==((msk>>i)&1))
					g[i+1][(j+k)/2]+=g[i][j]*Bi(cnt[i],k);
			}
			f[i]=g[46][0];
			for(int i=0;i<=46;i++)for(int j=0;j<=num/2;j++)
				g[i][j]=0;
		}
		for(int i=0;i<m;i++)for(int j=1;j<(1<<m);j++)
			if(j>>i&1)f[j]-=f[j-(1<<i)];
		for(int i=0;i<(1<<m);i++)cout<<f[i]<<' ';
		cout<<'\n';
	}
	return 0;
}