【问题描述】 小y是一个非常喜欢数码的同学，小z是一个特别喜欢取余操作的同学，有一天他们决定一起玩一个游戏来决定谁更加幸运。 小y说我决定幸运的数字它的数码中不应该含有0，并且它的数码和应该等于y。 例如y=4的时候，112、4、22等的数码和为4，对于小y来说就是幸运数字，但是40虽然数码和为4，但是含有0就不是y的幸运数字 小z说我决定幸运数字应该是对z取余等于0的。 例如z=2的时候 2的倍数0，2，4，6，8等就是小z的幸运数字。 于是他们叫来了他们的数学老师Kumb，希望他能够统计出同时满足他们两个人条件的幸运数字有多少。 幸运数的个数可能很大，请你对1000000007取模

【输入格式】 从文件 number.in 中读入数据 第一行 两个数一个y,一个z。

【输出格式】 输出到文件 number.out 中。 输出一行，含有一个整数 输出同时满足两个条件的幸运数的个数。

【样例输入1】 4 2 【样例输出1】 3 【样例1解释】 幸运数有 112 22 4

【数据范围及约定】 前20%数据 y<=10 0< z<=10 前100%数据 y<=50000 0<z<=500

附上本人丑陋的代码：

#include<iostream>
using namespace std;

int y, z, dp[50005][505];

template<typename T>
void fackInput(T& var) {
    var = 0;
    char c = getchar();
    bool neg = false;
    while (c == ' ' || c == '\n' || c == '\t') {
        c = getchar();
    }
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        var = var * 10 + (c - '0');
        c = getchar();
    }
    if (neg) {
        var = -var;
    }
}

int main() {
    fackInput(y);
    fackInput(z);
    dp[0][0] = 1;

    for (int i = 0; i <= y; i++) {
        for (int j = 0; j < z; j++) {
            for (int k = 1; k <= y - i && k <= 9; k++) {
                dp[i + k][(j * 10 + k) % z] += dp[i][j];
                dp[i + k][(j * 10 + k) % z] %= 1000000007;
            }
        }
    }

    printf("%d", dp[y][0]);

    return 0;
}