1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int n,m,k;12 int p[1000],h[1000],w[1000],v[1000],ptr;13 int dp[111][1100][1<<5];14 const int MOD = 1000000007;15 16 void prime_factor(int x){17     for(int i=2;i*i<=x;i++){18         while( x%i==0 ){19             p[i]++;20             x /= i;21         }22     }23     if( x!=1 ) p[x] = 1;24 }25 26 void handle(int x){27     w[++ptr] = x;28     for(int i=2;i*i<=x;i++){29         int t = 0;30         while( x%i==0 ){31             t ++;32             x /= i;33         }34         if( t&&t==p[i] ) v[ptr] |= (1<<(h[i]-1));35     }36     if( x!=1&&p[x]==1 ) v[ptr] |= (1<<(h[x]-1));37 }38 39 int main(){40     while(scanf("%d%d%d",&n,&m,&k)!=EOF){41         ptr = 0;42         memset(p,0,sizeof(p));43         memset(w,0,sizeof(w));44         memset(v,0,sizeof(v));45         memset(h,0,sizeof(h));46         prime_factor(m);47         int sn = 0;48         for(int i=0;i<1000;i++){49             if( p[i] ) {50                 h[i] = ++sn;51             }52         }53         for(int i=2;i*i<=m;i++){54             if( m%i==0 ) {55                 handle(i);56                 if( i*i!=m ) handle(m/i);57             }58         }59         handle(1);60         if(m!=1) handle(m);61         memset(dp,0,sizeof(dp));62         dp[0][0][0] = 1;63         for(int j=1;j<=k;j++){64             for(int i=1;i<=ptr;i++){65                 for(int k=0;k<=n;k++){66                     for(int mask=0;mask<(1<<sn);mask++){67                         if( k+w[i]<=n&&(mask|v[i])<(1<<sn) ){68                             dp[j][k+w[i]][mask|v[i]] = (dp[j][k+w[i]][mask|v[i]]+dp[j-1][k][mask])%MOD;69                         }70                     }71                 }72             }73         }74         printf("%d\n",dp[k][n][(1<<sn)-1]);75     }76     return 0;77 }