/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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
以下の 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
Score: 500 points
Problem Statement
N people are standing in a queue, numbered 1, 2, 3, ..., N from front to back. Each person wears a hat, which is red, blue, or green.
The person numbered i says:
- "In front of me, exactly A_i people are wearing hats with the same color as mine."
Assuming that all these statements are correct, find the number of possible combinations of colors of the N people's hats.
Since the count can be enormous, compute it modulo 1000000007.
Constraints
- 1 \leq N \leq 100000
- 0 \leq A_i \leq N-1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 A_3 ... A_N
Output
Print the number of possible combinations of colors of the N people's hats, modulo 1000000007.
Sample Input 1
6 0 1 2 3 4 5
Sample Output 1
3
We have three possible combinations, as follows:
- Red, Red, Red, Red, Red, Red
- Blue, Blue, Blue, Blue, Blue, Blue
- Green, Green, Green, Green, Green, Green
Sample Input 2
3 0 0 0
Sample Output 2
6
Sample Input 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
Sample Output 3
115295190