#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll binpow(ll a, ll b) {
ll r = 1;
while (b) {
if (b&1) r = (r*a)%MOD;
a = (a*a)%MOD;
b /= 2;
}
return r;
}
int valid(int n, int a[]) {
int b[n];
for (int i = 0; i < n; i++) b[i] = a[i];
for (int i = 0; i < n; i++) {
if (a[i] <= n) {
int s = (i-a[i]+1+n)%n;
for (int j = 0; j < n; j++) b[(s+j)%n] = j+1;
break;
}
}
bool ok = 1;
set<int> s;
for (int i = 0; i < n; i++) {
if (b[i] > a[i] || (b[i] < a[i] && a[i] <= n)) ok = 0;
s.insert(a[i]);
}
if (s.size() != n) ok = 0;
return ok;
}
int replacement(int n, int a[], int r[]) {
int b[n];
map<int, int> mp;
for (int i = 0; i < n; i++) {
b[i] = a[i];
if (a[i] > n) mp[a[i]] = i;
}
if (mp.size() == n) for (int i = 0; i < n; i++) b[i] = i+1;
else for (int i = 0; i < n; i++) {
if (a[i] <= n) {
int s = (i-a[i]+1+n)%n;
for (int j = 0; j < n; j++) b[(s+j)%n] = j+1;
break;
}
}
int l = 0;
if (mp.size()) for (int i = n+1; i <= mp.rbegin()->first; i++) {
if (mp.count(i)) r[l++] = b[mp[i]], b[mp[i]] = i;
else r[l++] = b[mp.rbegin()->second], b[mp.rbegin()->second] = i;
}
return l;
}
int countReplacement(int n, int a[]) {
if (!valid(n, a)) return 0;
ll ans = 1;
set<ll> s;
for (int i = 0; i < n; i++) if (a[i] > n) s.insert(a[i]);
if (s.size() == n) ans = n;
s.insert(n);
ll cnt = 0;
while (s.size() > 1) {
ll x = *s.rbegin(); s.erase(x);
cnt++;
ll y = *s.rbegin();
ans = (ans*binpow(cnt, max(0ll, x-y-1)))%MOD;
}
return ans;
}
