You are given a sequence consisting of non-negative integer numbers. In one move, you can take any two adjacent positive numbers and reduce both of them by 1. Sequence is called good if there is no valid move left.

Count the number of different good sequences that you can get from the given one. The answer may be large, so you have to give it modulo 109 + 7.

Input

The first line contains a single integer n (1 ≤ n ≤ 105), the length of the sequence.

The second line contains n non-negative integers: the initial sequence itself. Each element of the sequence does not exceed 300.

Output

Print the number of different good sequences modulo 109 + 7.