Divided to Palindromes

2 secs 1024 MB
sten's icon sten

問題文

長さ 2626 の非負整数列 A1,A2,,A26A_1, A_2, \dots, A_{26} が与えられます。

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

  • S, TS,\ T は空文字列または回文であり、'a' から 'z' の文字で構成される。
  • SS に含まれる文字 'a' の個数と TT に含まれる文字 'a' の個数の和が A1A_1 に等しい。
  • SS に含まれる文字 'b' の個数と TT に含まれる文字 'b' の個数の和が A2A_2 に等しい。
  • \dots
  • SS に含まれる文字 'z' の個数と TT に含まれる文字 'z' の個数の和が A26A_{26} に等しい。

制約

  • 0Ai1050 \leq A_i \leq 10^5
  • 入力はすべて整数

入力

A1 A2  A26A_1\ A_2\ \dots\ A_{26}

出力

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

サンプル

入力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.21)