# 【題解】Google Code Jam 2021 Round 2 pC Hidden Pancakes

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, n, a[100005], p = 1e9+7;
long long fac[100005], inv[100005];
vector <int> v[100005];

int power(int a, int b){
long long mul = a, ret = 1;
while (b){
if (b & 1){
ret *= mul;
ret %= p;
}
mul *= mul;
mul %= p;
b >>= 1;
}
return ret;
}
int c(int n, int k){
if (k > n) return 0;
return ((fac[n] * inv[k]) % p * inv[n-k]) % p;
}
int f(int l, int r, int tar){
if (l > r) return 1;
auto it = upper_bound(v[tar].begin(), v[tar].end(), r);
if (it == v[tar].begin()) return 0;
it--;
if (*it < l || r < *it) return 0;
long long ret = 1;
ret *= f(l, *it-1, tar);
ret %= p;
ret *= f(*it+1, r, tar+1);
ret %= p;
ret *= c(r-l, *it-l);
ret %= p;
//cout << l << " " << r << " " << tar << " " << ret << "\n";
return ret;
}

int main(){
cin >> t;
fac[0] = 1;
inv[0] = 1;
fac[1] = 1;
inv[1] = 1;
for (int i = 2; i <= 100000; i++){
fac[i] = (fac[i-1]*i) % p;
inv[i] = power(fac[i], p-2);
}
for (int Case = 1; Case <= t; Case++){
cin >> n;
for (int i = 1; i <= n; i++){
v[i].clear();
}
for (int i = 1; i <= n; i++){
cin >> a[i];
v[a[i]].push_back(i);
}
cout << "Case #" << Case << ": " << f(1, n, 1) << "\n";
}
}
```