题目描述

33DAI 想构造一棵 $n$ 层的二叉树，他希望第 $i$ 层有 $a_i$ 个节点（$a_1=1$，对于 $i\gt 1$，保证 $a_i\le a_{i-1}\times 2$，即保证有解）。

请你帮他算算有多少种可能的二叉树。方案数可能很大，请输出对 $10^9+7$ 取余后的结果。

输入格式

第一行一个数 $n$。

第二行为空格隔开的 $n$ 个整数 $a_1\sim a_n$。

输出格式

一个数，即方案数。方案数可能很大，请输出对 $10^9+7$ 取余后的结果。

3
1
2
1

4

  /\   /\   /\   /\
 /     \     /     \

3
1
2
2

6

  /\ | /\  |  /\ |  /\  | /\ | /\
 /\  |  /\ | / / | /  \ | \/ | \ \

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5000$，$1\le a_i\le 5000$。

• 子任务 1（30 分）：保证 $a_i\le 2$。
• 子任务 2（30 分）：保证 $n \le 4$。
• 子任务 3（40 分）：没有特殊性质。