Given n items and m people, each person gets wi gifts, and the number of solutions is not necessarily a prime number

First of all, we give the rest of the gifts to one person. The answer is obviously the same. w[++m]=n-w1-w2 - -wm
So the obvious answer is Cw1nCw2n − w1... Cwmn − w1 −... - wm − 1, that is, n!w1!w2!... wm!%P
What if P is not a prime number? Let's set P = Πi=1kpaii. Then we can calculate a remainder for each paii and get a system of modular linear equations. Then we can combine it with the Chinese remainder theorem. (because the two must be reciprocal, the common CRT is OK.)

Now our problem is how to calculate n!w1!w2!... wm!%paii. Because factorials may not be mutually prime with pi, there is no inverse element. gg. If we write the numerator and denominator in the form of xpki, then (x,pi)=1, we can calculate the inverse element. The power of the remaining pi can be directly reduced.

Let's consider how to calculate the part of mutual quality. Go to this typical example and you will: portal

I can't calculate the complexity anymore, qaq

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
#define ld long double
#define inf 0x3f3f3f3f
#define N 110
inline char gc(){
static char buf[1<<16],*S,*T;
return *S++;
}
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int P,nn,w[10],m,prime[N],mo[N],r[N],sum=0,tot=0;
inline void decomp(){
int x=P;
for(int i=2;i*i<=P;++i){
if(x%i) continue;prime[++tot]=i;mo[tot]=1;
while(x%i==0) x/=i,mo[tot]*=i;
}if(x!=1) prime[++tot]=x,mo[tot]=x;
}
inline void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,x,y);ll t=x;x=y;y=t-a/b*y;
}
inline int ksm(ll x,int k,int mod){
ll res=1;for(;k;k>>=1,x=x*x%mod) if(k&1) res=res*x%mod;return res;
}
inline int inv(int a,int mod){
ll x,y;exgcd(a,mod,x,y);return (x%mod+mod)%mod;
}
inline int multi(int n,int p,int mod){//Calculate n!% mod coprime
if(!n) return 1;ll res=1;
for(int i=2;i<mod;++i) if(i%p) (res*=i)%=mod;
res=ksm(res,n/mod,mod);
for(int i=2;i<=n%mod;++i) if(i%p) (res*=i)%=mod;
return res*multi(n/p,p,mod)%mod;
}
inline int calc(int n,int p,int mod){//n!/w1!w2!...wm! %mod
ll res=multi(n,p,mod);
for(int i=1;i<=m;++i){
ll tmp=multi(w[i],p,mod);
res=res*inv(tmp,mod)%mod;
}int k=0;//Calculation of non reciprocal parts
for(ll i=p;i<=n;i*=p) k+=n/i;
for(int i=1;i<=m;++i) for(ll j=p;j<=w[i];j*=p) k-=w[i]/j;
return res*ksm(p,k,mod)%mod;
}
inline int CRT(int n,int mod){
ll res=0;
for(int i=1;i<=n;++i){
ll a=P/mo[i],b=mo[i];
res+=r[i]*a%mod*inv(a,b);res%=mod;
}return res;
}
int main(){
//  freopen("a.in","r",stdin);