#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
/**********************/
#define ll long long
const int mod = 1e9 + 7;
int valid(int n, int inputSeq[])
{
int preval = -1;
for(int i =0; i<n; i++){
//cout << preval<<endl;
if(preval == -1){
if(inputSeq[i] <= n)
preval = inputSeq[i];
continue;
}
if(inputSeq[i] <=n){
if(preval == n){
if(inputSeq[i] != 1) return false;
}
else
if(inputSeq[i]!= preval+1) return false;
preval = inputSeq[i];
}
else{
//replacement, num can be anything
if(preval == n)
preval = 1;
else preval++;
}
}
if(inputSeq[n-1] == n)
return inputSeq[0] == 1;
else if(inputSeq[n-1] >n) return true;
else return inputSeq[n-1] +1 == inputSeq[0];
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
//debug second subtask, something weird is wrong but i am close
int preval = -1;
for(int i =n -1; i>=0; i--){
if(gondolaSeq[i] <=n){
preval = (n - i) + gondolaSeq[i];
if(preval> n) preval-=n;
break;
}
}
set<pair<int,int>> replace;
if(preval == -1){
//all of them were replaced
for(int i = 0; i<n; i++){
replace.insert({gondolaSeq[i], i+1});
}
}
else{
preval-=1;
//cout << preval<<endl;
for(int i =0; i<n; i++){
if(gondolaSeq[i] <=n){
preval = gondolaSeq[i];
}
else{
//replacement, num can be anything
if(preval == n){
replace.insert({gondolaSeq[i], 1});
preval = 1;
}
else {
replace.insert({gondolaSeq[i], ++preval});
}
}
}
}
int cnt = 0;
int prev = n;
for(pair<int,int> a : replace){
//cout <<a.first<<", "<<a.second<<endl;
replacementSeq[cnt] = a.second;
cnt++;
for(int i = prev+1; i< a.first; i++){
replacementSeq[cnt] = i;
cnt++;
}
prev = a.first;
}
return cnt;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
int preval = -1;
for(int i =n -1; i>=0; i--){
if(inputSeq[i] <=n){
preval = (n - i) + inputSeq[i];
if(preval> n) preval-=n;
break;
}
}
set<int> replace;
if(preval == -1){
//all of them were replaced
for(int i = 0; i<n; i++){
replace.insert(inputSeq[i]);
}
}
else{
preval-=1;
//cout << preval<<endl;
for(int i =0; i<n; i++){
if(inputSeq[i] <=n){
preval = inputSeq[i];
}
else{
//replacement, num can be anything
if(preval == n){
replace.insert(inputSeq[i]);
preval = 1;
}
else {
++preval;
replace.insert(inputSeq[i]);
}
}
}
}
ll ans = 1;
int prev = n+1;
int cnt = 0;
for( int a: replace){
ans *= pow((replace.size() - cnt), (a - prev)) ;
ans%= mod;
cnt++;
prev = a+1;
//cout << a<<": "<<ans<<endl;
}
return ans;
}
