Array Break

Given a positive integer array arr, count the pairs of non-negative integer arrays b and c, both of length n, such that b is non-decreasing, c is non-increasing, and b[i]+c[i]=arr[i] for every i. Output the answer modulo 1000000007.

The standard input/output, the ranges added by this site, and the examples follow this problem's description.

输入格式

The first line contains n (1≤n≤3000); the second line contains n integers (1≤arr[i]≤3000). The ranges and the modulus are taken from the original problem's constraints.

输出格式

Output the number of ordered array pairs (b,c) that satisfy the conditions, modulo 1000000007.

样例 1

输入：

3
2 3 2

输出：

4

样例 2

输入：

2
3 2

输出：

6

样例 3

输入：

1
1

输出：

2