题目背景

小蒟建立了一个城市，$\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$ 取模后的值。

4
1 1 1 1

28

3
1 2 3

68

提示

样例解释#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$ 则只存在直线道路和圆形道路。