Average Value Sequence

Consider a non-decreasing integer sequence $s_1, s_2, \ldots, s_{n+1}$ of length $n+1$ (that is, $s_i \le s_{i+1}$ for every $1 \le i \le n$).

Define the average sequence of $s$ as follows: for $1 \le i \le n$, $m_i = \frac{s_i + s_{i+1}}{2}.$

For example, if $S = (1, 2, 2, 4)$ then its average sequence is $M = \left(\frac{3}{2},\ 2,\ 3\right)$. The elements of an average sequence need not be integers, but in this problem we only consider cases where every element of the average sequence is an integer.

You are given a non-decreasing average sequence $m_1, m_2, \ldots, m_n$ of length $n$. Count the number of integer sequences $s_1, s_2, \ldots, s_{n+1}$ whose average sequence equals it.

The first line contains the length $n$ of the average sequence. ($2 \le n \le 5\,000\,000$)

Each of the next $n$ lines contains one element $m_i$ of the average sequence, in order. ($0 \le m_i \le 1\,000\,000\,000$; the sequence is non-decreasing.)

Print the number of integer sequences $s$ whose average sequence equals the given one.

For the first example ($m = (2, 5, 9)$), exactly the following four sequences exist: $(2, 2, 8, 10),\quad (1, 3, 7, 11),\quad (0, 4, 6, 12),\quad (-1, 5, 5, 13).$