Problem Description

$ N $ people are standing in a row, numbered from $ 1 $ to $ N $ in order from front to back. Each person is wearing a hat of one of three colors: red, blue, or green.

The person with number $ i $ made the following statement:

• "There are exactly $ A_i $ people in front of me wearing a hat of the same color as mine."

Assuming all statements are correct, determine the number of possible combinations of hat colors for the $ N $ people.

Since the answer can be very large, compute it modulo $ 1000000007 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ A_3 $ $ ... $ $ A_N $

Output Format

Output the number of possible combinations of hat colors for the $ N $ people modulo $ 1000000007 $.

Sample Input and Output

Sample Input #1

6
0 1 2 3 4 5

Sample Output #1

3

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

Notes/Hints

Constraints

• $1 \leq N \leq 100000$
• $0 \leq A_i \leq N-1$
• All values in the input are integers

Sample Explanation 1

The following $ 3 $ combinations are possible:
- Red, Red, Red, Red, Red, Red
- Blue, Blue, Blue, Blue, Blue, Blue
- Green, Green, Green, Green, Green, Green

见题面 Input 部分

见题面 Output 部分