Problem Description

In the year 2XXX, the countries of the world were arranged in a straight line. There are $ N $ countries, numbered $ 1, 2, ..., N $. For $ i = 1, 2, ..., N - 1 $, country $ i $ and country $ i + 1 $ are neighboring countries.

In this year's International Olympiad in Informatics, $ A_i $ contestants will participate from country $ i $. You are in charge of creating the seating chart for the competition as a member of the technical committee. Due to the long and narrow nature of the competition venue, the contestants will be assigned to $ A_1 + A_2 + ... + A_N $ seats arranged in a single row. To prevent cheating, contestants from the same country or neighboring countries must not be assigned to adjacent seats.

How many ways are there to assign the contestants to the seats? Since this number can be very large, you want to find it modulo $ 10007 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the number of ways to assign the contestants to the seats modulo $ 10007 $ in one line.

Sample Input and Output

Sample Input #1

4
2 1 1 1

Sample Output #1

4

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

Notes/Hints

Constraints

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

Subtasks

1. ($ 6 $ points) $ N ≦ 5 $, $ A_i ≦ 2 $ ($ 1 ≦ i ≦ N $)
2. ($ 14 $ points) $ N ≦ 10 $, $ A_i ≦ 3 $ ($ 1 ≦ i ≦ N $)
3. ($ 80 $ points) No additional constraints.

Sample Explanation 1

If we denote the $ 2 $ contestants from country $ 1 $ as $ 1 $ and $ 1' $, the $ 1 $ contestant from country $ 2 $ as $ 2 $, the $ 1 $ contestant from country $ 3 $ as $ 3 $, and the $ 1 $ contestant from country $ 4 $ as $ 4 $, the following $ 4 $ arrangements are possible:
- $ 1 $, $ 3 $, $ 1' $, $ 4 $, $ 2 $
- $ 1' $, $ 3 $, $ 1 $, $ 4 $, $ 2 $
- $ 2 $, $ 4 $, $ 1 $, $ 3 $, $ 1' $
- $ 2 $, $ 4 $, $ 1' $, $ 3 $, $ 1 $

Sample Explanation 2

In this input example, no seating chart satisfies the conditions.

Sample Explanation 3

In this input example, there are $ 24768 $ ways to assign the contestants to the seats, so the output is the remainder when divided by $ 10007 $, which is $ 4754 $.

见题面 Input 部分

见题面 Output 部分