Consider a nondecreasing sequence of integers $s_1,\dots ,s_{n+1}$ ($s_i\le s_{i+1}$ for $1\le i\le n$). The sequence $m_1,\dots ,m_n$ defined by $m_i=\frac{1}{2}(s_i+s_{i+1})$, for $1\le i\le n$, is called the mean sequence of sequence $s_1,\dots ,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_1,\dots ,m_n$, compute the number of nondecreasing sequences of $n+1$ integers $s_1,\dots ,s_{n+1}$ that have the given sequence $m_1,\dots ,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\le n\le 5000000)$. The remaining $n$ lines contain the sequence $m_1,\dots ,m_n$. Line $i+1$ contains a single integer $m_i$ $(0\le m_i\le 1000000000)$. You can assume that in $50\mathrm{\%}$ of the test cases $n\le 1000$ and $0\le m_i\le 20000$.

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.

Sample Input

3
2
5
9

Sample Output

4

Explanation for Sample Output

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$.