When Darth Vader gets bored, he sits down on the sofa, closes his eyes and thinks of an infinite rooted tree where each node has exactlyn sons, at that for each node, the distance between it an itsi-th left child equals to d_i. The Sith Lord loves counting the number of nodes in the tree that are at a distance at mostx from the root. The distance is the sum of the lengths of edges on the path between nodes.

But he has got used to this activity and even grew bored of it. 'Why does he do that, then?' — you may ask. It's just that he feels superior knowing that only he can solve this PRoblem.

Do you want to challenge Darth Vader himself? Count the required number of nodes. As the answer can be rather large, find it modulo10⁹?+?7.

The first line contains two space-separated integers n andx (1?≤?n?≤?10⁵,?0?≤?x?≤?10⁹) — the number of children of each node and the distance from the root within the range of which you need to count the nodes.

The next line contains n space-separated integersd_i (1?≤?d_i?≤?100) — the length of the edge that connects each node with itsi-th child.

Print a single number — the number of vertexes in the tree at distance from the root equal to at mostx.

3 31 2 3Output
8Note
Pictures to the sample (the yellow color marks the nodes the distance to which is at most three)
題目大意：有一棵樹(shù)，最開(kāi)始就一個(gè)根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有N個(gè)兒子，這個(gè)節(jié)點(diǎn)距離每個(gè)兒子的距離為di（1<=di<=100），問(wèn)你距離根節(jié)點(diǎn)距離小于等于X的節(jié)點(diǎn)個(gè)數(shù)有多少個(gè)。思路：1、如果對(duì)于統(tǒng)計(jì)個(gè)數(shù)，我們考慮dp，設(shè)定dp【i】表示距離根節(jié)點(diǎn)距離為i的節(jié)點(diǎn)個(gè)數(shù)。那么不難推出狀態(tài)轉(zhuǎn)移方程：dp【i】=Σdp【i-j】*len【j】；2、顯而易見(jiàn)，直接dp是會(huì)超時(shí)的，考慮優(yōu)化，既然我們有了遞推式，那么我們不妨介入矩陣優(yōu)化。然后矩陣快速冪就能夠做到O（LogX）的時(shí)間復(fù)雜度。3、既然有了dp遞推式，那么矩陣的構(gòu)造也就不難了：①因?yàn)樽畲箝L(zhǎng)度di==100，那么我們不妨將矩陣構(gòu)造為101*101的大小，最后一行用來(lái)轉(zhuǎn)移sum.因?yàn)槲覀円蟮氖铅瞕p【i】（0<=i<=X），而不是dp【X】；②那么接下來(lái)預(yù)處理出dp【0~100】；③那么有：③對(duì)應(yīng)求Sum【X】的時(shí)候，將第二個(gè)矩陣按照冪次增加即可。Ac代碼：
#include<stdio.h>#include<string.h>using namespace std;#define ll __int64#define mod 1000000007typedef struct Matrix{    ll mat[105][105];}matrix;matrix A,B,tmp,ans;ll len[105];ll dp[100000];Matrix matrix_mul(matrix a,matrix b){    matrix c;    memset(c.mat,0,sizeof(c.mat));    ll i,j,k;    for(ll i=0;i<101;i++)    {        for(ll j=0;j<101;j++)        {            for(ll k=0;k<101;k++)            {                c.mat[i][j]=(c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod)%mod;            }        }    }    return c;}Matrix matrix_quick_power(matrix a,ll k)//矩陣快速冪0.0{    matrix b;    memset(b.mat,0,sizeof(b.mat));    for(ll i=0;i<101;i++)    b.mat[i][i]=1;//單位矩陣b    while(k)    {        if(k%2==1)        {            b=matrix_mul(a,b);            k-=1;        }        else        {            a=matrix_mul(a,a);            k/=2;        }    }    return b;}int main(){    ll n,m;    while(~scanf("%I64d%I64d",&n,&m))    {        memset(len,0,sizeof(len));        memset(dp,0,sizeof(dp));        for(ll i=1;i<=n;i++)        {            ll x;            scanf("%I64d",&x);            len[x]++;        }        dp[0]=1;        for(ll i=1;i<=100;i++)        {            for(ll j=1;j<=i;j++)            {                dp[i]+=dp[i-j]*len[j];                dp[i]%=mod;            }        }        ll presum=0;        for(ll i=1;i<=m&&i<=100;i++)presum+=dp[i],presum%=mod;        if(m<=100)        {            printf("%I64d/n",presum+1);        }        else        {            memset(A.mat,0,sizeof(A.mat));            memset(tmp.mat,0,sizeof(tmp.mat));            for(ll i=0;i<100;i++)tmp.mat[i][0]=dp[i+1];            tmp.mat[100][0]=presum+1;            for(ll i=0;i<99;i++)            {                A.mat[i][i+1]=1;            }            for(ll i=0;i<100;i++)A.mat[99][i]=len[100-i];            for(ll i=0;i<100;i++)A.mat[100][i]=len[100-i];            A.mat[100][100]=1;            B=matrix_quick_power(A,m-100);            B=matrix_mul(B,tmp);            printf("%I64d/n",(B.mat[100][0]+mod)%mod);        }    }}