D - 1年生 (A First Grader) Editorial /

Time Limit: 10 sec / Memory Limit: 256 MB

配点: 100

問題

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 \leq N \leq 100) が書かれている. 2 行目には 0 以上 9 以下の整数が N 個 ,空白を区切りとして書かれている.

与えられる入力データの 60 %では,JOI君が作り,確かめることがで きる正しい等式の個数は 2^{31}-1 を超えない.また,与えられる入力データの全てにおいて,JOI君が作り,確かめることができる正しい等式の個数は 2^{63}-1 を超えない.

出力

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


入力例 1

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

出力例 1

10

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

  • 8+3-2-4+8-7-2-4-0+8=8
  • 8+3-2-4+8-7-2-4+0+8=8
  • 8+3+2+4-8-7+2-4-0+8=8
  • 8+3+2+4-8-7+2-4+0+8=8
  • 8+3+2-4+8-7+2+4-0-8=8
  • 8+3+2-4+8-7+2+4+0-8=8
  • 8-3+2+4-8+7+2+4-0-8=8
  • 8-3+2+4-8+7+2+4+0-8=8
  • 8-3+2-4+8+7+2-4-0-8=8
  • 8-3+2-4+8+7+2-4+0-8=8
を作り,確かめることができるので 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符号付き整数の範囲に収まらないことに注意せよ.