#include "bits/stdc++.h"
using namespace std;
#include "gondola.h"
int valid(int n, int arr[]) {
map<int, bool> mp;
vector<int> v(arr, arr+n);
auto it = min_element(v.begin(), v.end());
rotate(v.begin(), it, v.end());
for (int i = 0; i < n; ++i) {
if (mp[v[i]]) return 0;
mp[v[i]] = true;
if (v[i] <= n and i != v[i] - v[0]) return 0;
}
return 1;
}
int replacement(int n, int a[], int b[]) {
vector<int> v(a, a+n);
auto it = min_element(v.begin(), v.end());
int mn = *it, pos = it - v.begin(), mx = *max_element(v.begin(), v.end());
rotate(v.begin(), v.begin() + (pos - mn%n + 1 + n) % n, v.end());
map<int, int> mp;
for (int i = 0; i < n; ++i) {
mp[v[i]] = i+1;
}
for (int i = n+1; i <= mx; ++i) {
if (mp.count(i)) b[i-n-1] = mp[i];
else {
b[i-n-1] = mp[mx];
mp[mx] = i;
}
}
return mx - n;
}
using ll = long long;
const ll mod = 1e9+7;
#define sz(x) (int)x.size()
ll binexp(ll a, ll b) {
a %= mod;
ll ret = 1;
while (b) {
if (b&1) {
ret = (ret * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return ret;
}
int countReplacement(int n, int a[]) {
vector<int> v(a, a+n);
auto it = min_element(v.begin(), v.end());
rotate(v.begin(), it, v.end());
vector<int> v2 = v;
sort(v2.begin(), v2.end());
if (unique(v2.begin(), v2.end()) != v2.end()) return 0;
for (int i = 0; i < n; ++i) {
if (v[i] <= n and i != v[i] - v[0]) return 0;
}
ll ans;
if (v2[0] > n) ans = n;
else ans = 1;
vector<int> bigger;
bigger.push_back(n);
for (int i = 0; i < n; ++i) if (v[i] > n) bigger.push_back(v[i]);
sort(bigger.begin(), bigger.end());
for (int i = 1; i < sz(bigger); ++i) {
ans = (ans * binexp(sz(bigger) - i, bigger[i] - bigger[i-1] - 1)) % mod;
}
int ret = ans;
return ret;
}
