Вниз по піраміді

Вам подобаються числові піраміди? Зазвичай, для числової послідовності, яка є основою, потрібно побудувати решту "піраміди" знизу вгору: для кожної пари сусідніх чисел обчислюється їхня сума і записується над ними. Наприклад, для базової послідовності $[1,2,3]$ послідовність безпосередньо над нею буде $[3,5]$, а вершина піраміди буде $[8]$:

Однак мене не цікавить завершення піраміди — натомість я хочу заглибитися під землю. Таким чином, для послідовності з $n$ невід'ємних цілих чисел я запишу під нею послідовність з $n+1$ невід'ємних цілих чисел таку, що кожне число в початковій послідовності є сумою двох чисел, які я поставив під нею. Проте може існувати кілька можливих послідовностей, а можливо, і жодної, що задовольняє цій умові. Отже, чи можете ви визначити, з скількох послідовностей я зможу вибрати?

Вхідні дані

У першому рядку записана довжина $n(1\le n\le 10^6)$ базової послідовності.

Наступний рядок містить $n$ цілих чисел $a_1,...,a_n(0\le a_i\le 10^8$ для кожного $i$) — базову послідовність.

Вихідні дані

Виведіть кількість невід'ємних цілих послідовностей, для яких вхідна послідовність буде наступним рівнем у числовій піраміді.

Приклади