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 2

3 2 2

Sample Output

1

2

题意：

给出n,m,k,问k个数的和为n。最小公倍数为m的情况有几种

思路：

由于最小公倍数为m，能够知道这些数必定是m的因子，那么我们仅仅须要选出这全部的因子，拿这些因子来背包就能够了

dp[i][j][k]表示放了i个数，和为j。公倍数为k的情况有几种

可是又问题。首先的问题内存，直接存明显爆内存。那么我们须要优化

1.由于我如今放第i个数，必定是依据放好的i-1个数来计算的。我们仅仅须要用滚动数组来解决就可以

2.对于公倍数，必定不能超过m，而我全部这些m的因子中的数字，不管选哪些，选多少，他们的最小公倍数依旧是这些因子之中的，那么我们能够进行离散化

解决好了之后就是全然背包的问题了

#include <stdio.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <math.h>

using namespace std;

const int mod = 1e9+7;

int dp[2][1005][105];

int a[1005],len,pos[1005];

int n,m,k;

int hash[1005][1005];

int gcd(int a,int b)

{

    return b==0?

a:gcd(b,a%b);

}

int lcm(int a,int b)

{

    return a/gcd(a,b)*b;

}

int main()

{

    int i,j,x,y;

    for(i = 1; i<=1000; i++)//预处理最小公倍数

    {

        for(j = 1; j<=1000; j++)

            hash[i][j] = lcm(i,j);

    }

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        len = 0;

        memset(pos,-1,sizeof(pos));

        for(i = 1; i<=m; i++)

        {

            if(m%i==0)

            {

                a[len] = i;

                pos[i] = len++;//离散化

            }

        }

        memset(dp[0],-1,sizeof(dp[0]));

        dp[0][0][0] = 1;

        for(i = 1; i<=k; i++)

        {

            memset(dp[i%2],-1,sizeof(dp[i%2]));

            for(j = i-1; j<=n; j++)//由于最小必定放1,而我前面已经放了i-1个数了。前面的和最少必定是i-1

            {

                for(x = 0; x<len; x++)//枚举前面数字的公倍数

                {

                    if(dp[(i+1)%2][j][x]==-1)

                        continue;

                    for(y = 0; y<len && (a[y]+j)<=n; y++)//枚举这一位放哪些数

                    {

                        int r = hash[a[y]][a[x]];

                        int s = j+a[y];

                        if(pos[r]!=-1 && r<=m)

                        {

                            r = pos[r];

                            if(dp[i%2][s][r] == -1) dp[i%2][s][r] = 0;

                            dp[i%2][s][r]+=dp[(i+1)%2][j][x];

                            dp[i%2][s][r]%=mod;

                        }

                    }

                }

            }

        }

        if(dp[k%2][n][pos[m]]==-1)

            printf("0\n");

        else

            printf("%d\n",dp[k%2][n][pos[m]]);

    }

    return 0;

}