题目描述

  在纸上有一个长为 $n$ 的数列，第 $i$ 项值为 $a_i$。

  现在小 A 想要在这些数之间添加加号或乘号。问对于不同的 $2^{n-1}$ 种方案，

  所有答案的和是多少？

  由于数据范围较大，所以输出对 $1000000007$ 取模的结果。

输入格式

  输入第一行一个整数 $n$ 表示数列的长度。

  之后一行 $n$ 个整数，第 $n$ 个整数表示数列的第 $i$ 项 $a_i$。

输出格式

  一行，答案对 $1000000007$ 取模的结果。

输入样例

3
1 2 4

30

数据范围与约定

  对于30%的数据，$1≤n≤10,1≤a_i≤10^5$

  对于另外30%的数据，$1≤n≤1000,a_i=1$

  对于90%的数据，$1≤n≤1000,1≤a_i≤10^5$

  对于100%的数据，$1≤n≤100000,1≤a_i≤10^9$