피라미드 아래로

숫자 피라미드를 좋아하는가? 밑변을 나타내는 수열이 주어지면 보통은 피라미드의 나머지 부분을 아래에서 위로 쌓는다. 인접한 두 수의 합을 그 위에 적는 식이다. 예를 들어 밑변 수열이 [1, 2, 3]이라면 바로 위 수열은 [3, 5]가 되고, 피라미드의 꼭대기는 [8]이 된다.

하지만 나는 피라미드를 완성하는 데에는 관심이 없다. 그보다는 땅속으로 내려가고 싶다. 그래서 n개의 음이 아닌 정수로 이루어진 수열에 대해, 그 아래에 n + 1개의 음이 아닌 정수로 이루어진 수열을 적을 것이다. 원래 수열의 각 수가 그 아래에 적은 두 수의 합이 되도록 하는 것이다. 하지만 이 조건을 만족하는 수열은 여러 개일 수도 있고, 아예 없을 수도 있다. 그렇다면 선택할 수 있는 수열이 몇 개인지 알려줄 수 있겠는가?

입력은 다음과 같다.

• 정수 n (1 ≤ n ≤ 106)이 한 줄에 주어진다. n은 밑변 수열의 길이이다.
• n개의 정수 a1, . . . , an (각 i에 대해 0 ≤ ai ≤ 108)이 한 줄에 주어진다. 이 수열이 밑변 수열이다.

주어진 수열을 숫자 피라미드의 다음 층으로 가지는 음이 아닌 정수 수열의 개수를 정수 하나로 출력한다.