Codeforces Round 418 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

graphs

shortest paths

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. An unavoidable detour for home

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThose unwilling to return home from a long journey, will be affected by the oddity of the snail and lose their way. Mayoi, the oddity's carrier, wouldn't like this to happen, but there's nothing to do with this before a cure is figured out. For now, she would only like to know the enormous number of possibilities to be faced with if someone gets lost.

There are *n* towns in the region, numbered from 1 to *n*. The town numbered 1 is called the capital. The traffic network is formed by bidirectional roads connecting pairs of towns. No two roads connect the same pair of towns, and no road connects a town with itself. The time needed to travel through each of the roads is the same. Lost travelers will not be able to find out how the towns are connected, but the residents can help them by providing the following facts:

- Starting from each town other than the capital, the shortest path (i.e. the path passing through the minimum number of roads) to the capital exists, and is unique;
- Let
*l*_{i}be the number of roads on the shortest path from town*i*to the capital, then*l*_{i}≥*l*_{i - 1}holds for all 2 ≤*i*≤*n*; - For town
*i*, the number of roads connected to it is denoted by*d*_{i}, which equals either 2 or 3.

You are to count the number of different ways in which the towns are connected, and give the answer modulo 10^{9} + 7. Two ways of connecting towns are considered different if a pair (*u*, *v*) (1 ≤ *u*, *v* ≤ *n*) exists such there is a road between towns *u* and *v* in one of them but not in the other.

Input

The first line of input contains a positive integer *n* (3 ≤ *n* ≤ 50) — the number of towns.

The second line contains *n* space-separated integers *d*_{1}, *d*_{2}, ..., *d*_{n} (2 ≤ *d*_{i} ≤ 3) — the number of roads connected to towns 1, 2, ..., *n*, respectively. It is guaranteed that the sum of *d*_{i} over all *i* is even.

Output

Output one integer — the total number of different possible ways in which the towns are connected, modulo 10^{9} + 7.

Examples

Input

4

3 2 3 2

Output

1

Input

5

2 3 3 2 2

Output

2

Input

5

2 2 2 2 2

Output

2

Input

20

2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 3 3 2

Output

82944

Note

In the first example, the following structure is the only one to satisfy the constraints, the distances from towns 2, 3, 4 to the capital are all 1.

In the second example, the following two structures satisfy the constraints.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 09:17:07 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|