UVa 12034

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e3+10,Mod=10056; int c[N+100][N+100],f[N+100], n; void Init() { fo(i,0,N) { c[i][0]=c[i][i]=1; fo(j,1,i-1) c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod; } } int main() { Init() ; f[0]=1; fo(i,1,N) { f[i]=0; fo(j,1,i) f[i]=(f[i]+c[i][j]*f[i-j])%Mod; } int T; cin>>T; int kase=0; for(int kase = 1; kase <= T; kase++) { scanf("%d", &n); printf("Case %d: %d\n", kase, f[n]); } return 0; }