004 - 1年生 (A First Grader)

問題

JOI君は小学 1 年生である．JOI君は教わったばかりの足し算，引き算がとても好きで，数字が並んでいるのを見ると最後の 2 つの数字の間に「=」を入れ，残りの数字の間に必ず「+」または「-」を入れて等式を作って遊んでいる．例えば「8 3 2 4 8 7 2 4 0 8 8」から，等式「8+3-2-4+8-7-2-4-0+8=8」を作ることができる．

JOI君は等式を作った後，それが正しい等式になっているかを計算して確かめる．ただし，JOI君はまだ負の数は知らないし，20 を超える数の計算はできない．したがって，正しい等式のうち左辺を左から計算したとき計算の途中で現れる数が全て 0 以上 20 以下の等式だけがJOI君が確かめられる正しい等式である．例えば，「8+3-2-4-8-7+2+4+0+8=8」は 正しい等式だが，途中に現れる 8+3-2-4-8 が負の数なのでJOI君はこの等式が正しいかどうか確かめることができない．

入力として数字の列が与えられたとき，JOI君が作り，確かめることができる正しい等式の個数を求めるプログラムを作成せよ．

入力

入力ファイルは 2 行からなる．1 行目には並んでいる数字の個数を表す整数 N （3 ≦ N ≦ 100）が書かれている．2 行目には 0 以上 9 以下の整数が N 個，空白を区切りとして書かれている．

与えられる入力データの 60% では，JOI君が作り，確かめることができる正しい等式の個数は 2³¹-1 を超えない．また，与えられる入力データの全てにおいて，JOI君が作り，確かめることができる正しい等式の個数は 2⁶³-1 を超えない．

出力

JOI君が作り，確かめることができる正しい等式の個数を表す整数を 1 行で出力せよ．

入出力例

入力例 1

11
8 3 2 4 8 7 2 4 0 8 8

出力例 1

10

入力例 1 において，JOI君は 10 個の正しい等式

を作り，確かめることができるので 10 を出力する．

入力例 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

出力例 2

7069052760

入力例 2 において，答えが 32 bit符号付き整数の範囲に収まらないことに注意せよ．