#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n,int A[]){
for (int i(0);i < n;++i) --A[i];
set<int> S; for (int i(0);i < n;++i) if (A[i]<n) S.emplace((A[i]+n-i)%n);
sort(A,A+n); for (int i(1);i < n;++i) if (A[i-1]==A[i]) return 0;
return (int)(S.size()<=1);
}
int replacement(int n,int A[],int B[]){
int m = *max_element(A,A+n); vector C(A,A+n); sort(A,A+n); for (int i(0);i < n;++i) --A[i];
int x = 0; for (int i(0);i < n;++i) if (A[i]<n) x = (n-i+A[i])%n;
vector<int> D(n); for (int i(0);i < n;++i) D[lower_bound(A,A+n,C[i])-A] = (x+i)%n;
for (int i(n),k(lower_bound(A,A+n,n)-A);i < m;++i){
B[i-n] = D[k]+1,D[k] = i; if (D[k]==A[k]) ++k,++i;
}
return m-n;
}
int countReplacement(int n,int A[]){
if (!valid(n,A)) return 0;
sort(A,A+n); long long mod = 1000000007; for (int i(0);i < n;++i) --A[i];
auto modpow = [&mod](long long x,int i) -> int {
long long ret = 1;
while(i){
if (i&1) (ret *= x) %= mod;
(x *= x) %= mod,i>>=1;
}
return ret;
};
int m = A+n-lower_bound(A,A+n,n); long long ret = 1;
for (int i(0),p(n-1);i < m;p=A[n-m+i++]){
(ret *= modpow(m-i,A[n-m+i]-p-1)) %= mod;
}
return ret;
}
