#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define mod 1000000009

#define maxn 100009

using namespace std;

ll c[maxn];

void gcd(ll a,ll b,ll &d,ll &x,ll &y)

{

    if(b==)

    {

        d=a;

        x=;

        y=;

    }

    else

    {

        gcd(b,a%b,d,y,x);

        y-=x*(a/b);

    }

}

ll inv(ll a,ll n)

{

    ll d,x,y;

    gcd(a,n,d,x,y);

    return d==?(x+n)%n:-;

}

int main()

{

    int m,x,n;

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        int low=,up=;

        int loww=,upp=;

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

        {

            scanf("%d",&x);

            loww=n-up;

            upp=n-low;

            if(up>x&&low<x)

                low=(up-x)%;

            else if(up<=x)

                low=abs(up-x);

            else if(low>=x)

                low=abs(low-x);

            if(upp>x&&loww<x)

                loww=(upp-x)%;

            else if(upp<=x)

                loww=abs(upp-x);

            else if(loww>=x)

                loww=abs(loww-x);

            up=n-loww;

        }

//        printf("%d %d\n",low,up);

        c[]=;

        ll ans=;

        for(int i=; i<=n; i++)

        {

            c[i]=(c[i-]*(n-i+)%mod*inv(i,mod))%mod;

        }

        for(int i=low; i<=up; i+=)

        {

            ans+=c[i];

            ans%=mod;

        }

        printf("%I64d\n",ans);

    }

    return ;

}