You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Colorful Hats 2

题目描述

$N$ 个人站成一列，每个人都戴着一顶帽子，颜色为红、黄、绿的一种。第 $i$ 个人前面有 $A_i$ 个人戴着和他颜色相同的帽子。求出 $N$ 个人帽子颜色的所有组合方案。

答案对 $10^9+7$ 取模。

输入格式

输入共两行，第一行一个正整数 $N$ ，第二行 $N$ 个正整数 $A_1,A_2,...,A_n$。

$N$ $A_1$ $A_2$ $A_3$ $...$ $A_N$

输出格式

$N$ 个人帽子颜色的所有组合方案总数对 $10^9+7$ 取模的值。

样例 #1

样例输入 #1

6
0 1 2 3 4 5

样例输出 #1

3

样例 #2

样例输入 #2

3
0 0 0

样例输出 #2

6

样例 #3

样例输入 #3

54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

样例输出 #3

115295190

提示

数据范围

• $1\leq N \leq 100000$
• $0\leq a_i \leq N-1$
• $N$ 和 $a_i$ 均为整数。

样例解释1

以下 $3$ 种组合均符合条件。

• 红红红红红红
• 黄黄黄黄黄黄
• 绿绿绿绿绿绿