问题陈述
N 人们正在睡觉。潜伏,N-1 我决定用书绳把这些人绑在一起。
- 每根绳子可以通过将每一端绑在不同的人身上来连接两个人。
- 我希望每两个人都通过一根绳子直接或间接连接。 第
- i 人正好有 a_i 我想要连接书籍的字符串。
系绳子有多少种方法? 使用\rm{mod}\ 1,000,000,007 来求。
字符串应无法区分。约束
- 2 \leq N \leq 100000
- 1 \leq a_i \leq 3
输入格式
N a_1 : a_N
输出格式
示例输入 1
9 1 3 2 1 3 1 2 1 2
示例输出 1
1260