学步园

//hdu 4869
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
const int maxn=100010;
long long ans;
const long long mod=1000000009;
long long f[maxn];
int n;
int m;
//在某一个stage，对于不同的status，翻xi次时，翻之后1的个数的奇偶性不变。
//比如这个stage里最少会出现l个1，那么如果某一张牌本来应该1->0,实际翻了另一张牌使得0->1,那么该状态多出现了两个1，所以l,l+2,l+4均会存在。
//当最终状态有m个1时，方案数为C(n,m)=n!/(m!*(n-m)!)
//费马小定理:if p is a prime,a^(p-1)==1(mod p), so a^(p-2)==a^-1(mod p)
void setup()//预处理n!
{
    f[0]=1;
    f[1]=1;
    for(int i=2;i<maxn;i++)
    {
        f[i]=f[i-1]*i%mod;
    }
}

long long quickmod(long long a,long long b)
{
    long long as=1;
    while(b)
    {
        if(b&1)
        {
            as=(as*a)%mod;
            b--;
        }
        b/=2;
        a=((a%mod)*(a%mod))%mod;
    }
    return as;
}

int main()
{
   freopen("input.txt","r",stdin);
   int l,r=0;
   int lmin=0;//最少的1的个数
   int rmax=0;//最多的1的个数
   int x;
   setup();
   while(scanf("%d %d",&n,&m)!=EOF)
   {
       l=r=0;
       ans=0;
       for(int i=0;i<n;i++)
       {
           scanf("%d",&x);
           //find lmin
           if(x<=l) lmin=l-x;//l个1可以全部被翻成0
           else if(l<x&&x<=r)//l,l+3,l+4...等状态均存在，
           {
               if((l%2)==(x%2)) lmin=0;//可选择这一个stage中的l+2k==x的这个status全部翻成0
               else lmin=1;//否则，会多出一个，l+2k=x+1，只能将其中x个翻成1
           }
           else if(x>r) lmin=x-r;//x-r个0->1,最多r个1->0
           //find rmax
           if(r+x<=m) rmax=r+x;//把x个0变成1
           else if(l+x<=m&&r+x>m) rmax=(((l+x)%2)==m%2)?m:m-1;//l,l+2+x,l+4,+x...均存在，So存在一种状态将x个0翻成1后，达到m or m-1个1
           else if(l+x>m) rmax=2*m-x-l;//m-l个0->1,x-(m-l)个1->0,So l+(m-l)-(x-(m-l))
           l=lmin;
           r=rmax;
          // cout<<lmin<<" "<<rmax<<endl;
       }
       for(int i=lmin;i<=rmax;i+=2)
       {
           ans+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%mod;
       }
       printf("%I64d\n",ans%mod);
       //cout<<quickmod(3,3)<<endl;
  }
    return 0;
}