#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define ll long long#define mod 1000000009#define maxn 100009using namespace std;ll c[maxn];void gcd(ll a,ll b,ll &d,ll &x,ll &y){    if(b==0)    {        d=a;        x=1;        y=0;    }    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==1?(x+n)%n:-1;}int main(){    int m,x,n;    while(scanf("%d%d",&m,&n)!=EOF)    {        int low=0,up=0;        int loww=0,upp=0;        for(int i=0; i<m; i++)        {            scanf("%d",&x);            loww=n-up;            upp=n-low;            if(up>x&&low<x)                low=(up-x)%2;            else if(up<=x)                low=abs(up-x);            else if(low>=x)                low=abs(low-x);            if(upp>x&&loww<x)                loww=(upp-x)%2;            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[0]=1;        ll ans=0;        for(int i=1; i<=n; i++)        {            c[i]=(c[i-1]*(n-i+1)%mod*inv(i,mod))%mod;        }        for(int i=low; i<=up; i+=2)        {            ans+=c[i];            ans%=mod;        }        printf("%I64d\n",ans);    }    return 0;}