题目描述

给出 $n$ 个点，和每个点的度 $d_i$ 让你构造出一张无重边，无自环的无向图满足以下两条性质：

• 点 $1$ 到点 $i$ 仅有唯一一条最短路。

• 点 $1$ 到点 $i$ 的最短路长度大于等于点 $1$ 到点 $i-1$ 的最短路长度。

求能构成满足条件的无向图的个数？

输入格式

第一行一个整数 $n$，$3\le n\le 50$。

第二行 $n$ 个整数 $d_i$，$2\le d_i\le 3$。

输出格式

输出一个整数，表示答案对 $10^9+7$ 取余的结果。

4
3 2 3 2

1

5
2 3 3 2 2

2

5
2 2 2 2 2

2

20
2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 3 3 2

82944