#include <iostream>#include <string.h>#include <string>#include <fstream>#include <algorithm>#include <stdio.h>#include <vector>#include <queue>#include <set>#include <cmath>using namespace std;const double eps = 1e-8;const double pi=acos(-1.0);const int INF=0x7fffffff;unsigned long long uINF = ~0LL;#define MAXN 100007#define mod 1000000007typedef long long LL;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}int N,M,K;int LCM(int a,int b){ return a*b/gcd(a,b);}LL ans;int dp[2][1001][101],lcm[1001][1001];int pos[1001],num[1001];int main(){ for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++) lcm[i][j]=LCM(i,j); while(scanf("%d%d%d",&N,&M,&K)!=EOF) { ans=0;int cnt=0; memset(pos,-1,sizeof(pos)); for(int i=1;i<=M;i++) if(M%i==0) { num[cnt]=i; pos[i]=cnt++; } memset(dp[0],-1,sizeof(dp[0])); dp[0][0][0]=1; for(int i=1;i<=K;i++) { memset(dp[i&1],-1,sizeof(dp[i&1])); for(int j=i-1;j<=N;j++) { for(int k=0;k<cnt;k++) { if(dp[(i+1)&1][j][k]==-1)continue; for(int r=0;r<cnt&&j+num[r]<=N;r++) { int l=j+num[r]; int s=lcm[num[r]][num[k]]; if(s<=M&&pos[s]!=-1) { s=pos[s]; if(dp[i&1][l][s]==-1)dp[i&1][l][s]=0; dp[i&1][l][s]+=dp[(i+1)&1][j][k]; if(dp[i&1][l][s]>=mod)dp[i&1][l][s]-=mod; } } } } } printf("%dn",dp[K&1][N][pos[M]]==-1?0:dp[K&1][N][pos[M]]); } return 0;}
