你喜欢数字金字塔吗？给定一个代表底部的数字序列，通常你需要自底向上构建金字塔的其余部分：对于每一对相邻的数字，计算它们的和并写在它们上方。例如，给定底部序列 $[1, 2, 3]$，其上方的序列为 $[3, 5]$，金字塔的顶部为 $[8]$：

然而，我对完成金字塔不感兴趣——相反，我更愿意向地下延伸。因此，对于一个包含 $n$ 个非负整数的序列，我将在其下方写下一个包含 $n+1$ 个非负整数的序列，使得原序列中的每个数字都是我写在它下方的两个数字之和。然而，可能存在多个满足条件的序列，也可能一个都不存在。那么，你能告诉我我有多少种序列可以选择吗？

输入格式

输入包含： 一行包含整数 $n$ ($1 \le n \le 10^6$)，即底部序列的长度。 一行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 10^8$，对于每个 $i$)，构成底部序列。

输出格式

输出一个整数，表示有多少个非负整数序列，其下一层金字塔正好是输入的序列。

样例

样例输入 1

6
12 5 7 7 8 4

样例输出 1

2

样例输入 2

3
10 1000 100

样例输出 2

0