#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 235
#define MAXN 100005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
using namespace std;

ll n,m,ans,flag,cnt,tot;
ll fac[100005],rev[100005];

ll pow_mod(ll a,ll i,ll n)  // 快速幂取模
{
    if(i==0)return 1%n;
    ll temp=pow_mod(a,i>>1,n);
    temp=temp*temp%n;
    if(i&1)temp=temp*a%n;
    return temp;
}
void init() // 初始化
{
    fac[0]=rev[0]=1;
    for(ll i=1;i<=100000;i++)
    fac[i]=fac[i-1]*i%mod,rev[i]=pow_mod(fac[i],mod-2,mod);
}
ll C(ll n,ll m) // 求组合数取mod的值
{
    return (fac[n]*rev[m]%mod)*rev[n-m]%mod;
}

int main()
{
    ll i,j,t,x,le,ri;
    init();
    while(~scanf("%I64d%I64d",&n,&m))
    {
        le=ri=0;
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&x);
            ll u,v;
            if(x<=le) u=le-x;
            else if(x>le&&x<ri)
            {
                if((x+le)%2==0) u=0;
                else u=1;
            }
            else u=x-ri;

            if(x<=m-ri) v=ri+x;
            else if(x>m-ri&&x<=m-le)
            {
                if((x+le+m)%2==0) v=m;
                else v=m-1;
            }
            else v=le+(m-le)-(x-(m-le));
            le=u,ri=v;
        }
       // printf("le:%I64d ri:%I64d\n",le,ri);
        ans=0;
        for(i=le;i<=ri;i+=2)
        {
            ans+=C(m,i);
            ans%=mod;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}