#include<cstdio> #include<algorithm> #include<cstring> using std::sort; const long long maxn=1000,mod=1e9 + 7; long long n,k,done=1; long long ans[10*maxn+5]; long long sum[2][20005]; struct qst{ long long n,k,id; }Q[maxn*10+5]; inline void read(long long &x){ x=0;char c;long long f=1; do{ c=getchar();if(c=='-')f=-1; } while(c>'9'||c<'0'); do{ x=x*10+c-'0';c=getchar(); } while(c>='0'&&c<='9'); x*=f; } inline long long max(long long a,long long b){ return a>b?a:b; } long long d[2][20005]; void work(){ d[0][0]=1; sum[0][0]=1; for(register int i=1;i<=k;++i){ sum[0][i]=1; } for(register long long i=1;i<=n;++i){ for(register long long nk=0;nk<=k;++nk){ d[i&1][nk]=0; d[i&1][nk]=(sum[(i-1)&1][nk]-(nk-i>=0?sum[(i-1)&1][nk-i]:0)+mod)%mod; if(i==Q[done].n&&nk==Q[done].k){ ans[Q[done++].id]=d[i&1][nk]; } sum[i&1][nk]=((nk?sum[i&1][nk-1]:0)+d[i&1][nk])%mod; } } } inline bool cmp(qst a,qst b){ if(a.n!=b.n)return a.n<b.n; return a.k<b.k; } int main(){ long long T; read(T); for(register long long i=1;i<=T;++i){ read(Q[i].n); read(Q[i].k); n=max(n,Q[i].n); k=max(k,Q[i].k); Q[i].id=i; } sort(Q+1,Q+1+T,cmp); work(); for(register long long i=1;i<=T;++i){ printf("%lld\n",ans[i]); } return 0; }
#include<cstdio> #include<map> using std::map; const long long maxn=1e3; const long long mod=1000000007; long long n,k; long long a[maxn+5]; map<long long,long long>d; map<long long,bool> ment; long long mentd[maxn+5]; struct addo{ long long to,val; addo(long long to=0,long long val=0):to(to),val(val){} }add[maxn+5]; inline void read(long long &x){ x=0;char c;long long f=1; do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0'); do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f; } void work(){ for(register long long i=1;i<=n;++i){ read(a[i]); if(k%a[i]!=0)continue; long long lmentd=mentd[0],tadd=0; for(register long long j=1,y;j<=lmentd;++j){ if(k%(y=a[i]*mentd[j])!=0)continue; add[++tadd]=addo(y,d[mentd[j]]); if(!ment[y]){ mentd[++mentd[0]]=y; ment[y]=true; } } for(register long long j=1;j<=tadd;++j){ d[add[j].to]+=add[j].val; d[add[j].to]%=mod; } d[a[i]]++; d[a[i]]%=mod; if(!ment[a[i]]){ mentd[++mentd[0]]=a[i]; ment[a[i]]=true; } } printf("%lld\n",d[k]); } int main(){ long long T; read(T); while(T--){ read(n);read(k); work(); if(T){ ment.clear(); mentd[0]=0; } } return 0; }
#include<cstdio>
#include<cmath>
const long long mod=1e9+7;
const long long maxn=5e4;
long long g[320][maxn+5];
long long ans;
long long n,m;
int main(){
scanf("%lld",&n);
g[0][0]=1;
for(register int i=1;i<=319;++i){
for(register int j=i;j<=n;++j){
g[i][j]=(g[i][j-i]+g[i-1][j-i])%mod;
}
}
for(register int i=1;i<=319;++i){
ans+=g[i][n];
ans%=mod;
}
printf("%lld\n",ans);
return 0;
}