English · Original
Chinese · Translation
Formal · Original
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.
## 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 109 + 7.
[samples]
## 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.
<center></center>In the second example, the following two structures satisfy the constraints.
<center></center>
不愿从长途旅行中返回家园的人，将受到蜗牛的怪异影响而迷失方向。作为怪异载体的Mayoi不希望这种情况发生，但在找到解药之前她也无能为力。目前，她只想知道如果有人迷路，将会面临多少种巨大的可能性。
该地区有 #cf_span[n] 个城镇，编号从 #cf_span[1] 到 #cf_span[n]。编号为 #cf_span[1] 的城镇被称为首都。交通网络由连接城镇对的双向道路构成。没有两条道路连接相同的城镇对，也没有道路连接城镇与自身。通过每条道路所需的时间相同。迷路的旅行者无法得知城镇之间的连接方式，但居民可以向他们提供以下信息：
你需要计算城镇之间连接的不同方式的数量，并对 #cf_span[109 + 7] 取模。两种连接方式被认为是不同的，当且仅当存在一对 #cf_span[(u, v)]（#cf_span[1 ≤ u, v ≤ n]），使得其中一种方式中城镇 #cf_span[u] 和 #cf_span[v] 之间有道路，而另一种方式中没有。
输入的第一行包含一个正整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 50]）——城镇的数量。
第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[d1, d2, ..., dn]（#cf_span[2 ≤ di ≤ 3]）——分别表示与城镇 #cf_span[1, 2, ..., n] 相连的道路数量。保证所有 #cf_span[di] 的总和为偶数。
请输出一个整数——城镇可能的不同连接方式的总数，对 #cf_span[109 + 7] 取模。
在第一个示例中，以下结构是唯一满足约束条件的结构，城镇 #cf_span[2, 3, 4] 到首都的距离均为 #cf_span[1]。
在第二个示例中，以下两种结构满足约束条件。
## Input
输入的第一行包含一个正整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 50]）——城镇的数量。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[d1, d2, ..., dn]（#cf_span[2 ≤ di ≤ 3]）——分别表示与城镇 #cf_span[1, 2, ..., n] 相连的道路数量。保证所有 #cf_span[di] 的总和为偶数。
## Output
请输出一个整数——城镇可能的不同连接方式的总数，对 #cf_span[109 + 7] 取模。
[samples]
## Note
在第一个示例中，以下结构是唯一满足约束条件的结构，城镇 #cf_span[2, 3, 4] 到首都的距离均为 #cf_span[1]。在第二个示例中，以下两种结构满足约束条件。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 50 $.
Let $ \mathbf{d} = (d_1, d_2, \dots, d_n) \in \{2,3\}^n $ be the degree sequence of an undirected simple graph with $ n $ vertices, where $ \sum_{i=1}^n d_i $ is even.
**Constraints**
1. $ d_1 \geq 2 $, $ d_i \in \{2,3\} $ for all $ i \in \{1, \dots, n\} $.
2. $ \sum_{i=1}^n d_i $ is even.
**Objective**
Count the number of simple undirected graphs on $ n $ labeled vertices with degree sequence $ \mathbf{d} $, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. An unavoidable detour for home",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF814E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "不愿从长途旅行中返回家园的人，将受到蜗牛的怪异影响而迷失方向。作为怪异载体的Mayoi不希望这种情况发生，但在找到解药之前她也无能为力。目前，她只想知道如果有人迷路，将会面临多少种巨大的可能性。\n\n该地区有 #cf_span[n] 个城镇，编号从 #cf_span[1] 到 #cf_span[n]。编号为 #cf_span[1] 的城镇被称为首都。交通网络由连接城镇对的双向道路构成。没有两条道路连...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 50 $. \nLet $ \\mathbf{d} = (d_1, d_2, \\dots, d_n) \\in \\{2,3\\}^n $ be the degree sequence of an undirected simple graph with $ n $ vertic...",
"is_translate": false,
"language": "Formal"
}
]
}