The next line contains n integers Xi(0<=Xi<=m).
Output Output the required answer modulo 1000000009 for each test case, one per line.
Sample Input
3 4
3 2 3
3 3
3 2 3
Sample Output
8
3
HintFor the second example:
0 express face down,1 express face up
Initial state 000
The first result:000->111->001->110
The second result:000->111->100->011
The third result:000->111->010->101
So, there are three kinds of results(110,011,101)
Author FZU
Source 2014 Multi-University Training Contest 1
题解
这几天最烦这种，“姿势对着，就是不过”的题了。。。比赛的时候我想的算法是：“O(NlgN)排序 - O(N)计算答案区间 - O(N)对答案求和”。但是TLE了。。。后来又仔细的想了想，其实根本不需要排序，直接就能O(N)计算答案区间。然后重写写了份，纠结了半天的位运算处理奇偶性之后终于过了。
我慢慢一步一步说我的算法是怎么来的。
抽象
这个模型非常的巧妙，因为是卡片的翻转，那么每个卡片就有两种状态（正面'1'和反面'0'）。
那么能不能把这个实际例子抽象出来呢？
当然是可以的了！
首先引入符号M(n, k)：表示，n张卡片中，只有k张正面的所有的可能的集合。
其次我引入一种建立在M(n, k)中的元素上的二元运算，翻转运算，用乘法(*)表示。
为什么是二元运算呢？我们慢慢地考虑翻转状态。“从4张卡片中先翻转3张。”这句话的意思是不是可以理解成“_M(4, 0) * _M(4, 3)”呢？我用前置的下划线表示一个这个集合的元素。也就是说，这个表达式就是从没有正面开始发生状态转移，结果我们暂时不考虑，状态转移的方法是通过“翻转3张”这个操作。换句话说，一次乘法运算相当于一种累计翻转。第一次翻转的是0张，所以所有的答案是M(4, 0)；第二次翻转的是3张，所以所有的答案是M(4, 3)。两次翻转一累计，就是我们的答案了。
再次强调，一次乘法运算就相当于累计翻转，当然多次的乘法运算（比如先翻3张，再翻2张，最后再翻3张）也可以看做多次的累计翻转。即，针对一张特定的卡片，如果它翻转了偶数次，就相当于没有翻转；同样翻转了奇数次的就相当于翻转了一次。
然后这个运算的作用范围是什么呢？没错，是刚刚定义的符号M(n, k)的所有元素的全体，也就是：G = {x | x ∈ M(n, k), k = 0, 1, 2, 3, ..., n.}。
其次我们接着去关心这个运算的一些性质：（为了方便，以后称这个运算为乘法）
首先这个运算满足结合律。即，对任意的G中的元素a, b, c，a * b * c = a * (b * c)。这个不多提，独立证明。其次这个运算有单位元e = M(n, 0)。即，对任意的G中的元素a， a * e = e * a = a。这个可以简单地发现。再者这个运算有逆元a-1 = a。即，对任意的G中的元素a， a * a-1 = a-1 * a = e。因为一个翻转只需再执行一次自己的翻转就行了。最后这个运算有交换律。即，对任意的G中的元素a, b, c，a * b = b * a。因为翻转的顺序是不定的，可以先翻转a张，再翻转b张；也可以先翻转b张，再翻转a张。
所以，针对G和构建在G上的运算*就是一个阿贝尔群（交换群）。
但是这个代数系统显然不够好。我们应当接着去拓展他。
换句话说，刚才，我们仅仅研究两个元素去做这个运算的性质，现在我们去研究两个集合，去做这个运算的性质。当然，首先我们从结果入手，尝试去寻找规律。
比如这次运算：M(n, x1) * M(n, x2)，为了方便分析结果，我们假设x1 >= x2，会产生什么样的结果呢？
回归刚才的定义，M(n, x1)表示有y1 := x1个正面，和y2 := (n - x1)个反面。那么下一步要对x2个卡片进行翻转。我们假设，它对i个上一次翻转过的卡片进行再翻转，对j个没有翻转过的卡片进行翻转。这样就有C(y1, i) + C(y2, j)种可能，同时当然还要满足组合数的公式等等。这里生成的结果都有什么呢？假设最后的正面有z个，原本有y1个正面，先减少i个，在增加j个。又因为i + j = x2，x1 >= x2，所以有 x1 - x2 <= z <= min(n, (n - x1) + (n - x2))。而且，如果你是在草稿纸上写了过程的话，你会发现，本来 z = y1 - i + j = x1 - i + (x2 - i) = x1 + x2 - 2 * i。也就是，z是一个公差为2的等差数列。
为了方便理解，我引入加法符号+，表示集合的并运算。
举个具体的例子吧：
M(4, 3) * M(4, 2) = M(4, 1) + M(4, 3)
M(8, 5) * M(8, 3) = M(8, 2) + M(8, 4) + M(8, 6) + M(8, 8)
M(8, 4) * M(8, 6) = M(8, 3) + M(8, 5) + M(8, 7)
不知道大家看出一个规律没有，就是关于结果序列的奇偶性。如果x1与x2同时是偶数，结果是一个奇数的序列；同时为奇数，结果是一个偶数序列；一奇一偶，结果是奇数序列。 还有一个规律，如果有多次的乘法运算，岂不是要对每一个生成的结果进行再一次乘法运算？没错的。这里严格意义上，引入加法，就同时引入了分配率的概念，相当于建立了一个环。不过用处不大，只是方便理解而已。
回到刚才多次乘法运算的问题，如果每一个都去乘，答案就会很慢很慢，因为这里相当于进行的是对一个N的数据展开成(N / 2)的一组新数据，会指数爆炸的。但是举个例子，假设我计算的是这组乘法：
M(8, 4) * M(8, 6) * M(8, 3)
第一次乘法的运行结果时：
M(8, 4) * M(8, 6) = M(8, 3) + M(8, 5) + M(8, 7)
接着去逐项去乘：
M(8, 3) * M(8, 3) = M(8, 0) + M(8, 2) + M(8, 4) + M(8, 6)
M(8, 5) * M(8, 3) = M(8, 2) + M(8, 4