You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

土拨鼠小北写了一个递归函数：

int f(int i,int j) 
{
	if(i==n) return a[j];
	else return (f(i+1,j)+f(i+1,j+1))%1000000007;
}

其中，$n$ 是一个int类型的变量，$a[ \ ]$ 是一个int类型的数组。 现在，给你 $n$ 和 $a$数组，请你求出 $f(1,1)$ 的值。

Format

Input

第一行一个正整数，$n$。第二行 $n$ 个数，表示 $a$数组。

Output

$f(1,1)$ 的值。

Samples

4
1 3 2 9

25

5
18 76 34 98 20

938

Limitation

样例1解释：

f(1,1)=25
f(2,1)=9  f(2,2)=16
f(3,1)=4  f(3,2)=5  f(3,3)=11
f(4,1)=1  f(4,2)=3  f(4,3)=2  f(4,4)=9

• 请注意读入效率。
• $1≤n≤10^6$
• $a_i≥1$，$a_i*1000000007≤long \ long \ limit$

1s, 1024KiB for each test case.