Olympiad in Informatics

Consider a nondecreasing sequence of integers s₁, . . . ,s_n+1 (s_i ≤ s_i+1 for 1 ≤ i ≤ n). The sequence m₁, . . . ,m_n defined by m_i = 1/2 (s_i+s_i+1), for 1 ≤ i ≤ n, is called the mean sequence of sequence s₁, . . . ,s_n+1. For example, the mean sequence of sequence 1, 2, 2, 4 is the sequence 1.5, 2, 3. Note that elements of the mean sequence can be fractions. However, this task deals with mean sequences whose elements are integers only.

Given a nondecreasing sequence of n integers m₁, . . . ,m_n, compute the number of nondecreasing sequences of n+ 1 integers s₁, . . . ,s_n+1 that have the given sequence m₁, . . . ,m_n as mean sequence.

Task

Write a program that:

• reads from the standard input a nondecreasing sequence of integers,
• calculates the number of nondecreasing sequences, for which the given sequence is mean sequence,
• writes the answer to the standard output.

Input

The first line of the standard input contains one integer n (2 ≤ n ≤ 5 000 000 ). The remaining n lines contain the sequence m₁, . . . ,m_n. Line i+ 1 contains a single integer m_i (0 ≤ m_i ≤ 1 000 000 000 ). You can assume that in 50% of the test cases n ≤ 1 000 and 0 ≤ m_i 6 20 000 .

Output

Your program should write to the standard output exactly one integer — the number of nondecreasing integer sequences, that have the input sequence as the mean sequence.

Example

For the input data:
3
2
5
9
the correct result is:
4

Indeed, there are four nondecreasing integer sequences for which 2 ,5 ,9 is the mean sequence. These sequences are:

• 2 ,2 ,8 ,10 ,
• 1 ,3 ,7 ,11 ,
• 0 ,4 ,6 ,12 ,
• -1 ,5 ,5 ,13 .

Note: For now there are only 17 not very big test cases, remaining ones will be added in a month, all submissions will be rejudged.