本题是原题的数据加强版，修改了$\red{数据范围}$和$\red{模数}$。

题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共$\red{m}$盆。通过调查顾客的喜好,小明列出了顾客最喜欢的$\red{n}$种花,从$\red{1}$到$\red{n}$标号。

为了在门口展出更多种花,规定第i种花不能超过 $\red{a_i}$ 盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算,一共有多少种不同的摆花方案。

输入格式

输入文件共$\red{2}$行。第一行包含两个正整数$\red{n}$和$\red{m}$,中间用一个空格隔开。第二行有$\red{n}$个整数,每两个整数之间用一个空格隔开,依次表示$\red{a_1、a_2、……a_n}$。

输出格式

输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对1e9+9取模的结果。

样例

样例输入

2 4
3 2

样例输出

2

数据范围与提示

【输入输出样例说明】

有 $\red{2}$ 种摆花的方案，分别是$\red{(1，1，1，2)， (1，1，2，2)}$。括号里的 $\red{1}$ 和 $\red{2}$ 表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

数据范围

$对于 \red{100\%}数据，有 \red{0 < n \leq 1000，0 < m \leq 1000，0 \leq a_i \leq 1000。}$