AT_sumitb2019_e Colorful Hats 2

有 $N$ 个人排成一列，按照从前到后的顺序编号为 $1, 2, 3, \ldots, N$。每个人都戴着一顶帽子，帽子的颜色可以是红色、蓝色或绿色中的一种。 现在，第 $i$ 号的人说： - “在我前面，戴着和我同样颜色帽子的人恰好有 $A_i$ 个。” 假设所有人的发言都是真实的，请你计算 $N$ 个人帽子颜色的所有可能组合数。 由于答案可能非常大，请输出对 $1000000007$ 取模后的结果。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $A_3$ $\ldots$ $A_N$

输出 $N$ 个人帽子颜色的所有可能组合数，对 $1000000007$ 取模后的结果。

### 限制条件 - $1 \leq N \leq 100000$ - $0 \leq A_i \leq N-1$ - 输入中的所有值均为整数 ### 样例解释 1 可以考虑以下 $3$ 种组合： - 红，红，红，红，红，红 - 蓝，蓝，蓝，蓝，蓝，蓝 - 绿，绿，绿，绿，绿，绿 由 ChatGPT 4.1 翻译