An unavoidable detour for home
Contest: Codeforces Round 418 (Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, graphs, shortest paths

Those 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 li be the number of roads on the shortest path from town i to the capital, then li ≥ li - 1 holds for all 2 ≤ i ≤ n;
- For town i, the number of roads connected to it is denoted by di, 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 109 + 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 format:
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 d1, d2, ..., dn (2 ≤ di ≤ 3) — the number of roads connected to towns 1, 2, ..., n, respectively. It is guaranteed that the sum of di over all i is even.

Output format:
Output one integer — the total number of different possible ways in which the towns are connected, modulo 109 + 7.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
4
3 2 3 2

Example output:
1

Example input:
5
2 3 3 2 2

Example output:
2

Editorial:
Let's make it intuitive: the graph looks like this.
Formally, if we find out the BFS levels of the graph, it will look like a tree with extra edges among vertices of the same level, and indices of vertices in the same level form a consecutive interval. Therefore we can add vertices from number 1 to number n to the graph, without missing or violating anything.
Consider the case when we want to add vertex u to a graph formed by the first u - 1 vertices. The state only depend on the current and the previous level (We can't start level l + 1 without finishing level l - 1, thus there are only two unfinished levels).
The whole thing is described by four parameters: the number of "1-plug" (having one outgoing edge that is not determined) and "2-plug" (similar definition) vertices in the previous and the current level. Let f[u][p1][p2][c1][c2] be the number of ways to build the graph with the first u vertices, with p1 "1-plug" vertices and p2 "2-plug" vertices in the previous level, and c1 and c2 in the current one respectively.
For vertex u, we must choose one vertex v in the previous layer and connect u to it. For the remaining degree(s) of u, we can choose either to connect them to vertices in the same layer, or simply leave them for future. Also, we may start a new level if p1 = p2 = 0. This gives us an O(1) recursion.
There are O(n5) states, giving us a time complexity of O(n5) and a space complexity of O(n4) if the first dimension is reused. The constant factor can be rather small (since p1 + p2 + c1 + c2 ≤ n). See solution 1 for detailed recursion.
Let's try to improve this a bit. Instead of adding one vertex at a time, we consider the layer as a whole. Let f[c0][c1][c2] be the number of ways to build a single level with c0 vertices (their "plugs" don't matter), and connect it to the previous layer which has c1 "1-plug" vertices and c2 "2-plug" ones. Recursion over f can be done in O(1). Then let g[l][r] be the number of ways to build the graph with vertices from l to n, while vertices from l to r form the first level — note that this level should be connected to another previous one. The recursion over g can be done in O(n). The final answer should be g[2][d1] since the capital must be directly connected to vertices from 2 to d1. The overall time complexity is O(n3). Huge thanks to Nikolay Kalinin (KAN) for this!
Bonus. Figure out the O(n4) solution :P