Description：

有 $n$ 种大小为 $1$ 的物品和有 $m$ 种大小为 $2$ 的物品，每种都有无限个，求填满大小为 $k$ 的背包的方案数 $\bmod P$ 。

$1\leqslant n,m\leqslant 10^5,1\leqslant k\leqslant 10^{12}​$

Solution：

最后答案的生成函数为 $(\frac1{1-x})^n(\frac1{1-x^2})^m$ ，我们乘上 $(\frac1{1+x})^n(1+x)^n$ ，那么答案就是 $(\frac1{1-x^2})^{n+m}(1+x)^n$ ，然后我们可以枚举右边那一项的次数为 $i\in[0,n]$ ，他的系数就是 $\binom n i$ ，然后左边就是 $n+m$ 个物品，每个物品体积为 $2$ ，要求装满 $k-i$ 的背包的方案数，也就是把 $\frac{k-i}2$ 划分为可空的 $n+m$ 的集合的问题，显然可以用隔板法，模数不大用卢卡斯定理求组合数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXP 1000000

typedef long long ll;

int n,m,MOD;

ll k;

int fac[MAXP + 5],inv[MAXP + 5];

int power(int a,int b){int r = 1;while(b > 0){if(b & 1)r = 1ll * r * a % MOD;a = 1ll * a * a % MOD,b = b >> 1;}return r;}

void init()

{

	fac[0] = 1;

	for(int i = 1;i < MOD;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	inv[MOD - 1] = power(fac[MOD - 1],MOD - 2);

	for(int i = MOD - 2;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	return;

}

int C(int n,int m)

{

	if(n < m)return 0;

	return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

int Lucas(ll n,ll m)

{

	if(n < m)return 0;

	if(n < MOD)return C(n,m);

	else return 1ll * Lucas(n / MOD,m / MOD) * C(n % MOD,m % MOD) % MOD;

}

int divide(ll n,ll m)

{

	return Lucas(n + m - 1,m - 1);

}

int query(int n,int m,ll k,int MOD)

{

	int ans = 0;

	for(int i = 0;i <= n;++i)

	{

		if((k - i) % 2 == 1)continue;

		ans = (ans + 1ll * Lucas(n,i) * divide((k - i) / 2,n + m) % MOD) % MOD;

	}

	return ans;

}

void work()

{

	scanf("%d%d%lld%d",&n,&m,&k,&MOD);

	init();

	printf("%d\n",query(n,m,k,MOD));

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}