← 返回题目列表

Codeforces · 814/E

E. 回家不可避免的绕路

中文机器翻译题面 查看原题

长途跋涉不愿回家的人,会受到蜗牛怪异的影响而迷失方向。 Mayoi,这个奇怪的东西的携带者,不希望这种事发生,但在找到治疗方法之前,这件事没有任何关系。目前,她只想知道如果有人迷路,会面临多少种可能性。

该地区有n个城镇,编号从1到n。编号为 1 的城镇称为首都。交通网络由连接城镇的双向道路组成。没有两条道路连接同一对城镇,也没有道路将城镇与其本身连接起来。通过每条道路所需的时间是相同的。迷路的旅行者将无法找出城镇如何连接,但居民可以通过提供以下事实来帮助他们:

- 从首都以外的各个城镇出发,到首都的最短路径(即经过最少路数的路径)都存在,并且是唯一的;
- 设 li 为从城镇 i 到首都的最短路径上的道路数量,则 li ≥ li - 1 对于所有 2 ≤ i ≤ n 成立;
- 对于城镇 i,与其连接的道路数量用 di 表示,等于 2 或 3。

你要计算城镇连接的不同方式的数量,并给出模 109 + 7 的答案。如果存在一对 (u, v) (1 ≤ u, v ≤ n),其中一个城镇 u 和 v 之间有一条道路,但另一个城镇之间没有道路,则两种连接城镇的方式被认为是不同的。

输入

输入的第一行包含一个正整数 n (3 ≤ n ≤ 50) — 城镇数量。

第二行包含 n 个空格分隔的整数 d1, d2, ..., dn (2 ≤ di ≤ 3) — 分别连接到城镇 1, 2, ..., n 的道路数量。保证所有 i 的 di 之和是偶数。

输出

输出一个整数——城镇连接的不同可能方式的总数,模 109 + 7。

示例

输入 #1

4
3 2 3 2

输出 #1

1

输入 #2

5
2 3 3 2 2

输出 #2

2

输入 #3

5
2 2 2 2 2

输出 #3

2

输入#4

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

输出#4

82944

注意

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

在第二个示例中,以下两个结构满足约束。