CF814E.An unavoidable detour for home

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 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 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.

那些不愿从漫长旅途中归家的人，会受到蜗牛怪异现象的影响而迷路。作为该怪异现象宿主的“百物语”，不希望此类事情发生，但在找到解决办法之前也无能为力。目前，她只想知道：若有人迷路，将可能面临多少种巨大的可能性。

该地区共有 $n$ 座城镇，编号为 $1$ 至 $n$。编号为 $1$ 的城镇称为首都。交通网络由连接若干对城镇的双向道路构成。任意两条道路不会连接相同的城镇对，且不存在连接某城镇与其自身的道路。每条道路的通行耗时均相同。迷路的旅行者无法得知各城镇之间的连接方式，但当地居民可提供如下信息以协助他们：

• 从除首都外的每一座城镇出发，均存在一条通往首都的最短路径（即经过道路数最少的路径），且该路径唯一；
• 记 $l_i$ 为从城镇 $i$ 到首都的最短路径所经道路数，则对所有 $2 \le i \le n$，均有 $l_i \ge l_{i-1}$；
• 对于城镇 $i$，其相连的道路数记为 $d_i$，且 $d_i$ 的取值仅为 $2$ 或 $3$。

你需要计算城镇间连接方式的不同总数，并将结果对 $10^9 + 7$ 取模。若存在一对城镇 $(u, v)$（其中 $1 \le u, v \le n$），使得在一种连接方式中城镇 $u$ 与 $v$ 之间有道路相连，而在另一种中则无，则认为这两种连接方式不同。

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.

输入的第一行包含一个正整数 $n$（$3 \leq n \leq 50$）—— 城镇的数量。

第二行包含 $n$ 个用空格分隔的整数 $d_1, d_2, ..., d_n$（$2 \leq d_i \leq 3$）—— 分别表示与城镇 $1, 2, ..., n$ 相连的道路数量。保证所有 $d_i$ 的总和为偶数。

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

输出一个整数——城镇之间所有可能的不同连接方式的总数，对 $10^9 + 7$ 取模。

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.

在第一个例子中，以下结构是唯一满足约束条件的结构，城镇 2、3、4 到首都的距离均为 1。

在第二个例子中，以下两种结构满足约束条件。