← 返回题目列表

AtCoder · nyc2015_5

E. 字符串

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

问题陈述

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