配点: $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$ で割った余りを出力してください。

6
0 1 2 3 4 5

3

以下の $3$ 通りの組合せが考えられます。

• 赤, 赤, 赤, 赤, 赤, 赤
• 青, 青, 青, 青, 青, 青
• 緑, 緑, 緑, 緑, 緑, 緑

3
0 0 0

6

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

115295190