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 31 -1 を超えない.また,与えられる入力データの全てにおいて,JOI君が作り,確かめることができる正しい等式の個数は 2 63 -1 を超えない.

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

생성자가 기록되지 않았습니다.

출처 JOI 2011 Preliminary