City Tour

• Time : O(nlogn)
• Space : O(n)

long long fac[1010];
long long mod = 1e9 + 7;

long long fact(long long n) {
    if(n == 1) return 1;
    if(fac[n]) return fac[n];
    return fac[n] = n * fact(n-1) % mod;
}

long long modpow(long long n, long long x) {
    if(x == 0) return 1;
    long long res = modpow(n,x>>1);
    res = (res * res) % mod;
    if(x & 1) res = (res * n) % mod;
    return res;
}
int Solution::solve(int A, vector<int> &B) {
    sort(begin(B), end(B));
    vector<long long> gap {B[0] - 1};
    for(int i = 1; i < B.size(); i++) {
        gap.push_back(B[i] - B[i-1] - 1);
    }
    gap.push_back(A-B.back());
    long long res = 1, sum = 0, inv = 1;
    for(int i = 0; i < gap.size(); i++) {
        if(!gap[i]) continue;
        if(0 < i and i < gap.size() - 1) res = res * modpow(2,gap[i]-1) % mod;
        sum += gap[i];
        inv = inv * fact(gap[i]) % mod;
    }
    return res * fact(sum) % mod * modpow(inv, mod-2) % mod;
}