Math Magic

---

Time Limit: 3 Seconds      

Memory Limit: 32768 KB

---

Yesterday, my teacher taught us about math: +, -, *, /, GCD, LCM... As you know, LCM (Least common multiple) of two positive numbers can be solved easily because of a * b = GCD (a, b) * LCM (a, b).

In class, I raised a new idea: "how to calculate the LCM of K numbers". It's also an easy problem indeed, which only cost me 1 minute to solve it. I raised my hand and told teacher about my outstanding algorithm. Teacher just smiled and smiled...

After class, my teacher gave me a new problem and he wanted me solve it in 1 minute, too. If we know three parameters N, M, K, and two equations:

1. SUM (A₁, A₂, ..., A_i, A_i+1,..., A_K) = N 

2. LCM (A₁, A₂, ..., A_i, A_i+1,..., A_K) = M

Can you calculate how many kinds of solutions are there for A_i (A_i are all positive numbers). I began to roll cold sweat but teacher just smiled and smiled.

Can you solve this problem in 1 minute?

Input

There are multiple test cases.

Each test case contains three integers N, M, K. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ 100)

Output

For each test case, output an integer indicating the number of solution modulo 1,000,000,007(1e9 + 7).

You can get more details in the sample and hint below.

Sample Input

4 2 23 2 2

Sample Output

12

Hint

The first test case: the only solution is (2, 2).

The second test case: the solution are (1, 2) and (2, 1).

这题时间卡的真紧啊！

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAXN 1005#define mod 1000000007int lca[MAXN][MAXN],dp[2][MAXN][MAXN],vec[MAXN];int gcd(int a,int b){    if(a==0)return b;    return gcd(b%a,a);}int main(){    int n,m,k,i,j,now,no,k1,j1,ans,ii;    for(i=1;i<=1000;i++)        for(j=i;j<=1000;j++)            lca[j][i]=lca[i][j]=i/gcd(i,j)*j;    while(scanf("%d%d%d",&n,&m,&no)!=EOF)    {        now=0;        //memset(dp,0,sizeof(dp));        ans=0;        vec[ans++]=1;        for(i=2;i<=m;i++)        {            if(m%i==0)            vec[ans++]=i;        }        for(ii=0;ii<=n;ii++)            for(j=0;j
        
         n)                        break;                        k1=lca[k][j1];                       if(k1>m||m%k1!=0)                        continue;                        dp[now][j1+j][k1]+=dp[now^1][j][k];                        dp[now][j1+j][k1]%=mod;                    }                }        }        printf("%d\n",dp[now][n][m]%mod);    }    return 0;}