Divided to Palindromes

2 secs 1024 MB
sten

問題文


長さ の非負整数列 が与えられます。

文字列のペア であって、以下の条件をすべて満たすものの個数を で割ったあまりで求めてください。

  • は空文字列または回文であり、'a' から 'z' の文字で構成される。
  • に含まれる文字 'a' の個数と に含まれる文字 'a' の個数の和が に等しい。
  • に含まれる文字 'b' の個数と に含まれる文字 'b' の個数の和が に等しい。
  • に含まれる文字 'z' の個数と に含まれる文字 'z' の個数の和が に等しい。

制約


  • 入力はすべて整数

入力


出力


条件を満たすペアの個数を で割ったあまりで出力してください。

サンプル


入力1
2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力1
10

"" "abba", "" "baab", "b" "aba", "bb" "aa", "a" "bab", "bab" "a", "aa" "bb", "aba" "b", "abba" "", "baab" "" が条件を満たします。


入力2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力2
1

条件を満たす文字列のペアは "" "" のみです。


入力3
3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力3
12

入力4
3 2 3 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力4
0

入力5
4 3 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力5
120

Submit


Go (1.14)