#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

bool used[333333];
int mp[333333];

int main(){

	ll n;cin >> n;
	vector<ll> v(n);
	set<ll> s;
	REP(i,n){
		cin >> v[i];
		s.insert(v[i]);
	}

	if(s.size() == 1){
		cout << s.count(1) << endl;
		return 0;
	}

	deque<int> deq;
	deque<int> ldeq;
	ll now = -1,pla = 0,st = -1,ans = 1,malen = 0,nlen = 0;
	bool flag = true;
	vector<pair<pair<ll,ll>,pair<ll,ll>>> seica;
	while(1){
		if(pla == st)break;
		if(v[pla] != now){
			now = v[pla];
			deq.push_back(now);
			ldeq.push_back(nlen);
			if(deq.size() > 3)deq.pop_front();
			if(ldeq.size() > 3)ldeq.pop_front();
			if(deq.size() == 3) {
				if(flag){
					st = pla;
					flag = false;
				}
				if(used[deq[1]]){
					cout << 0 << endl;
					return 0;
				}
				seica.PB(MP(MP(deq[1],ldeq[2]),MP(deq[0],deq[2])));
				used[deq[1]] = true;
				malen = max(malen,nlen);
			}
			nlen = 1;
		}
		else{
			nlen++;
		}
		pla = (pla + 1) % n;
	}
	sort(ALL(seica));
	if(malen > seica[0].FI.SE){
		cout << 0 << endl;
		return 0;
	}

	now = 0;
	pla = 0;
	for(ll i = 1;i <= n;i++){
		pla += mp[i];
		if(now < seica.size() && seica[now].FI.FI == i){
			if(i < seica[now].SE.FI){
				mp[max(seica[now].SE.SE,i+1)] += seica[now].FI.SE - 1;
			}
			else if(i < seica[now].SE.SE){
				mp[max(seica[now].SE.SE,i+1)] += seica[now].FI.SE;
				pla--;
			}
			else{
				ans *= malen - seica[now].FI.SE + 1;
				ans %= MOD;
				mp[max(seica[now].SE.SE,i+1)] += seica[now].FI.SE - 1;
			}
			now++;
		}
		else{
			ans *= pla;
			ans %= MOD+
			pla--;
		}
	}

	cout << ans << endl;

	return 0;
}
