#include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<y?x:y) #define mmin(x,y) (x0){ if(n&1)res=res*a%mod; a=a*a%mod; n>>=1; } return res; } ll fac[100010],finv[100010]; ll comb(ll n,ll r){ if(n<0||r<0||n>N>>D>>K; ll S=K-N; ll res=0; rep(i,N+1){ ll nS=S-i*D; if(nS<0)continue; ll v=comb(nS+(N-1),N-1)*comb(N,i)%mod; if(i%2==0) (res+=v)%=mod; else (res+=mod-v)%=mod; } cout<