UOJ Logo

NOI.AC

1S 256MB

#124. B

统计

【题目描述】

我们有一个长度无穷的数列$A[i]$,其中初始的时候只有数列前$n$ 项可能不为 $0$,从第$n+1$ 项开始都为 $0$。

我们可以做如下操作任意次。

选择一个 $i$ 满足 $a[i]>0$ 且 $a[i+1]>0$,然后将 $a[i]$减 $1$,$a[i+1]$减1,$a[i+2]$加 $1$。

我们现在想要知道,通过任意次做这个操作,能得到多少种不同的数列。

两个数列不同当且仅当这两个数列存在一个对应位置上的数不同。答案非常大,输出答案对 $1000000007$ 取模。

(注意这个不同数列的个数要包括初始的数列,可通过样例 2 理解)

【输入格式】

输入文件 B.in

第一行一个整数 n。

第二行 n 个整数,第 i 个整数代表 $a[i]$。

【输出格式】

输出文件 B.out

输出一行一个整数表示方案数对 $1000000007$ 取模的结果。

【样例输入 1】

3 
2 3 1

【样例输出 1】

9 

【样例输入 2】

2 
2 2

【样例输出 2】

4 

【数据范围】

对于$40%$的数据,$n \le 8,a[i] \le 4$

对于另外$30%$的数据,$n=2,a[i] \le 50$

对于$100%$的数据,$n \le 50,0 \le a[i] \le 50$