有一棵n叉树，深度是无限的，每个结点有n个儿子。从左到右编号为1到n号儿子，第i号儿子离该结点的距离是di。现在要统计一下距离根结点不超过x的结点有多少个。

数字比较大对 109 + 7 取余后输出。

样例解释：

图中黄色的结点是距离根不超3的。

Input

单组测试数据。第一行有两个整数n和x (1≤n≤10^5,0≤x≤10^9)，表示每个结点的儿子数目，以及上文提到的x。第二行有n个整数d1,d2,d3,…,dn (1≤di≤100)。

Output

输出结果占一行。

Input示例

样例输入13 31 2 3

Output示例

样例输出18 暴力DP很好想，f[i]表示到根节点深度为i的有几个,f[i]=sigma(f[i-j]*cnt[j]),j=1->100 这样就可以用个矩阵来描述啦，意会一下

 

放上大佬NBC的代码就是上面的思路，对于边界的情况我不是很懂，如有大佬看懂请尽快发表。

#include 
     
      #include
      
       using namespace std;int I(){    int r = 0, c;    do c = getchar(); while (c < 48 || c > 57);    do r = (r << 3) + r + r + (c - 48), c = getchar(); while (c > 47 && c < 58);    return r;}const long long MOD = 1000000007;int N, X, cnt[101];long long ans[101], bit[101][101];void push(){    static long long tmp[101];    for (int i = 0; i < 101; i++)    {        tmp[i] = 0;        for (int j = 0; j < 101; j++)            if ((tmp[i] += bit[i][j] * ans[j]) > 8223372024854775771LL)                tmp[i] %= MOD;    }    for (int i = 0; i < 101; i++)        ans[i] = tmp[i] % MOD;}void twice(){    static long long tmp[101][101];    for (int i = 0; i < 100; i++)        for (int j = 0; j < 100; j++)        {            tmp[i][j] = 0;            for (int k = 0; k < 101; k++)                if ((tmp[i][j] += bit[i][k] * bit[k][j]) > 8223372024854775771LL)                    tmp[i][j] %= MOD;        }    for (int i = 0; i < 101; i++)        for (int j = 0; j < 101; j++)            bit[i][j] = tmp[i][j] % MOD;}int main(){    N = I(), X = I();    for (int i = 1; i <= N; i++)        cnt[I()]++;    ans[0] =ans[100] = 1;    for (int i = 0; i < 99; i++)        bit[i + 1][i] = 1;    for (int i = 0; i < 100; i++)        bit[0][i] = cnt[i + 1];    bit[0][100] = bit[100][100] = 1;    for(int i=0;i<=50;i++)    {        for(int j=0;j<=50;j++)            cout<
       
        <<' ';        cout<
        
         >= 1)    {        if (X & 1)            push();        twice();    }    printf("%lld\n", ans[0]);    return 0;}