Reduce the Sequence#6449
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 . 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 10^9 + 7.
The first line contains a single integer (1 \leq n \leq 10^5), the length of the sequence.
The second line contains non-negative integers: the initial sequence itself. Each element of the sequence does not exceed .
Print the number of different good sequences modulo 10^9 + 7.
Example 1
Example 2