Skip to content
Sign in

座席 (Seats)

Unrated
日本語

Language

Contribute a translation
Time limit
5000 ms
Memory limit
256 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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

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

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

Constraints

  • \(1 ≦ N ≦ 100\)
  • \(1 ≦ A_i ≦ 4\) (\(1 ≦ i ≦ N\))

Input

入力は以下の形式で標準入力から与えられる．

\(N\)
\(A_1\) \(A_2\) \(...\) \(A_N\)

Output

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

Subtasks

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

Examples

Sample input 1
4
2 1 1 1
Sample output 1
4

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

  • \(1\), \(3\), \(1'\), \(4\), \(2\)
  • \(1'\), \(3\), \(1\), \(4\), \(2\)
  • \(2\), \(4\), \(1\), \(3\), \(1'\)
  • \(2\), \(4\), \(1'\), \(3\), \(1\)
Sample input 2
5
1 2 3 2 1
Sample output 2
0

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

Sample input 3
6
1 2 3 3 2 1
Sample output 3
4754

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

Notes

JOI 2019 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source