分数: 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