← 返回题目列表

AtCoder · sumitb2019_e

E. 彩色帽子 2

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

分数: 500 点

问题陈述

N 人们正在排队,编号 1, 2, 3, ..., N 从前到后。每个人都戴着一顶帽子,帽子有红色、蓝色或绿色。

编号为 i 说:

  • “在我面前,正是 A_i 人们戴着和我颜色相同的帽子。”

假设所有这些陈述都是正确的,请找出可能的颜色组合数 N 人们的帽子。

由于计数可能很大,请对其进行模计算 1000000007.

约束

  • 1 \leq N \leq 100000
  • 0 \leq A_i \leq N-1
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 A_3 ... A_N

输出

打印颜色的可能组合数 N 人的帽子,模数 1000000007.


示例输入 1

6
0 1 2 3 4 5

示例输出 1

3

我们有三种可能的组合,如下:

  • 红,红,红,红,红,红
  • 蓝色,蓝色,蓝色,蓝色,蓝色,蓝色
  • 绿,绿,绿,绿,绿,绿

示例输入 2

3
0 0 0

示例输出 2

6

示例输入 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