P5880 【地理】划分

小蒟建立了一个城市，$\texttt{TA}$ 凭借优（cu）异（bi）的人文地理素养，管理着城市并进行规划。

对于一座新建的城市，可以将其视为一片连通的区域。 现在，小蒟需要建造一些道路，将城市分为若干片互不连通的区域。 首先，小蒟要建造 $a_1$ 条主干道。主干道是一条贯通整个城市的直线。 接着，小蒟要建造 $a_2$ 个环岛。环岛是一条首尾相接的圆形道路。 然后，小蒟要建造一些道路网络。这些道路网络包括 $a_3$ 条正三角形道路（即三条道路连成一个封闭的三角形），$a_4$ 条正四边形道路……$a_n$ 条正 $n$ 边形道路。 小蒟希望用这些道路将城市划分为尽可能多片互不连通区域。可是他不会计算最多能划分成为多少个区域，所以他只能来求助你。 由于最后的答案可能很大很大，你只需要输出答案对 $10^9+7$ 取模的值。

第一行，一个正整数 $n$，代表小蒟的计划中边数最多的道路网络是几边形。 第二行，$n$ 个整数，为 $a_{1\dots n}$。

一行一个整数，表示答案对 $10^9+7$ 取模后的值。

#### 样例解释#1 如下图所示：  #### 数据范围 对于 $20\%$ 的数据：$1\le n \le 10^3$，$0 \le a_i \le 100$。 对于 $100\%$ 的数据：$1\le n \le 3 \times 10^6$，$0 \le a_i \le 10^3$。 **注意内存限制，你的 UKE 很有可能就是 MLE**。 **若 $n=1$ 则只存在直线道路，若 $n=2$ 则只存在直线道路和圆形道路。**