#include "gondola.h"
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int valid(int n, int inputSeq[])
{
set<int> S;
int prev = -1, prev_pos = -1;
for(int i = 0; i < n; i++)
{
if(S.find(inputSeq[i]) != S.end()) return 0;
S.insert(inputSeq[i]);
if(inputSeq[i] > n) continue;
if(prev != -1)
{
if((i - prev_pos + n) % n != (inputSeq[i] - prev + n) % n) return 0;
}
prev = inputSeq[i];
prev_pos = i;
}
return 1;
}
int* gondolaSeqGlobal;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
gondolaSeqGlobal = gondolaSeq;
vector<int> I(n);
for(int i = 0; i < n; i++) I[i] = i;
sort(I.begin(), I.end(), [] (int x, int y)
{
return gondolaSeqGlobal[x] < gondolaSeqGlobal[y];
});
int pos1 = 0;
for(int i = 0; i < n; i++)
{
if(gondolaSeq[i] <= n)
{
pos1 = (i + 1 - gondolaSeq[i] + n) % n;
break;
}
}
int l = 0;
if(gondolaSeq[ I[0] ] > n)
{
replacementSeq[l] = ((I[0] - pos1 + n) % n) + 1;
l++;
}
for(int j = n+1; j < gondolaSeq[ I[0] ]; j++)
{
replacementSeq[l] = j;
l++;
}
for(int i = 1; i < n; i++)
{
if(gondolaSeq[ I[i] ] > n)
{
replacementSeq[l] = ((I[i] - pos1 + n) % n) + 1;
l++;
}
for(int j = max(n+1, gondolaSeq[ I[i-1] ] + 1); j < gondolaSeq[ I[i] ]; j++)
{
replacementSeq[l] = j;
l++;
}
}
return l;
}
long long mod = 1e9 + 7;
long long pow(long long b, long long p)
{
if(p == 0) return 1;
if(p % 2) return (b * pow(b, p-1)) % mod;
long long temp = pow(b, p/2);
return (temp * temp) % mod;
}
long long ll(int x)
{
return (long long)(x);
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
int original = 0;
for(int i = 0; i < n; i++) if(inputSeq[i] <= n) original = 1;
sort(inputSeq, inputSeq + n);
int x;
for(x = 0; x < n && inputSeq[x] <= n; x++);
if(x == n) return 1;
long long res = pow(n-x, inputSeq[x] - n - 1);
for(x++; x < n; x++)
{
res = (res * pow(ll(n-x), ll(inputSeq[x] - inputSeq[x-1] - 1))) % ll(mod);
}
if(!original)
{
for(long long m = 1; m <= n; m++) res = (res * m) % mod;
}
return int(res);
}
