JOI logo
第18回日本情報オリンピック 予選6

2018年12月10日
情報オリンピック日本委員会

問題
  座席 (Seats) (配点 100点)
  時間制限 : 5sec / メモリ制限 : 256MB

問題文

2XXX 年,世界の国は直線状に並んでいた.N 個の国があり,1, 2, ..., N の番号が付けられている.i = 1, 2, ..., N - 1 に対し,国 i と国 i + 1 が互いに隣国である.

この年の国際情報オリンピックでは,国 i からは A_i 人の選手が参加する.国際情報オリンピックの技術委員のあなたは,競技での座席表を作成する担当である.競技会場が細長いため,一列に並んだ A_1 + A_2 + ... + A_N 個の座席に選手たちを割り当てることになった.不正防止のため,同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない.

選手たちを座席に割り当てる方法は何通りあるだろうか.この数は非常に大きくなる可能性があるので,それを 10007 で割った余りを求めたい.

制約

入力・出力

入力
入力は以下の形式で標準入力から与えられる.
N
A_1 A_2 ... A_N

出力
選手たちを座席に割り当てる方法の数を 10007 で割った余りを 1 行で出力せよ.

小課題

  1. (6 点) N ≦ 5A_i ≦ 2 (1 ≦ i ≦ N)
  2. (14 点) N ≦ 10A_i ≦ 3 (1 ≦ i ≦ N)
  3. (80 点) 追加の制約はない.

入出力例

入力例 1
4
2 1 1 1

出力例 1
4

1 から参加する 2 人の選手を 11',国 2 から参加する 1 人の選手を 2,国 3 から参加する 1 人の選手を 3,国 4 から参加する 1 人の選手を 4 で表すことにすると,選手たちを座席に割り当てる方法としては,以下の 4 通りの並べ方が考えられる:


入力例 2
5
1 2 3 2 1

出力例 2
0

この入力例では,条件を満たす座席表は存在しない.


入力例 3
6
1 2 3 3 2 1

出力例 2
4754

この入力例では,選手たちを座席に割り当てる方法は 24768 通りあるため,それを 10007 で割った余りである 4754 を出力する.