#pragma comment(linker, "/stack:200000000")
                #pragma GCC optimize ("Ofast")
                #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
                #include <iostream>
                #include <iomanip>
                #include <sstream>
                #include <cstring>
                #include <vector>
                #include <deque>
                #include <queue>
                #include <set>
                #include <map>
                #include <valarray>
                #include <iterator>
                #include <functional>
                #include <limits>
                #include <algorithm>
                #include <numeric>
                #include <cmath>
                #include <cassert>
                #include <unordered_map>
                #include <unordered_set>
                #include <stack>
                using namespace std;
                #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
                 #define trace(x) cerr << #x << ": " << x << " " << endl;
             
                typedef int64_t ll;
             
                #define endl '\n'
                #define int ll
                ll mod=1e9+7;
                ll mod1=1e9+5;
                
                ll power(ll a,ll b)
                {
                    if(b==0) return 1;
                    else if(b%2==0)
                        return power((((a%mod)*(a%mod))%mod),b/2)%mod;
                    else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
                }
                bool check(string s,string s1)
                {
                    int j=0;
                    for(int i=0;i<s.length();++i)
                    {
                        if(j==3)
                            break;
                        if(s[i]==s1[j])
                        {
                            j++;
                        }
                    }
                    if(j==3)
                        return 1;
                    return 0;

                }
             int32_t main()
                {
                IOS
              
                
                int n;
                cin>>n;
                int x=0;
                int a[n];

                for(int i=0;i<n;++i)
                    {
                        cin>>a[i];
                        if(a[i]==0)
                            x++;
                    }
                    if(x>3)
                    {
                        cout<<0;
                        return 0;
                    }
                   
                    int count[n+1];
                    memset(count,0,sizeof(count));
                    int ans=1;
                    int maxi[n+1];
                    memset(maxi,0,sizeof(maxi));
                    for(int i=0;i<n;++i)
                        maxi[a[i]]++;
                    for(int i=0;i<n;++i)
                    {
                        
                        if(a[i]==0)
                        {
                            count[a[i]]++;
                            continue;
                        }
                            ans=ans*(count[a[i]-1]-count[a[i]]);
                            ans%=mod;
                        count[a[i]]++;
                    }
                    if(x!=1)
                 ans=ans*6;
             if(x==1)
                ans=ans*3;
                    ans%=mod;
                    cout<<ans;

                
            }

Measured memory_bytes: 2560