Submission #1165416

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long lli;
const lli MOD = 1000000007;
lli exeuclid(lli a,lli aa,lli x,lli xx,lli y,lli yy){
	lli q;
	if(a == 0) return aa > 0 ? xx : -xx;
	q = aa / a;
	return exeuclid(aa - q * a,a,xx - q * x,x,yy - q * y,y);
}

lli invarse(lli x){
	return (exeuclid(MOD,x,0,1,1,0) + MOD) % MOD;
}


lli factrial(lli x){
	static lli dp[10000];
	if(dp[x]) return dp[x];
	if(x == 0) 	return dp[x] = 1;
				return dp[x] = (factrial(x-1) * x) % MOD;
}
lli factrial(lli from,lli to){
    lli ret = 1;
    for(lli i = from;i <= to;i++){
        ret *= i;
        ret %= MOD;
    }
    return ret;
}

lli combination(lli n,lli k){
    return (factrial(n-k+1,n)*invarse(factrial(k))) % MOD;
}
lli n;
vector<lli> a;
lli now,c;
lli ans = 1;

int main(){
    cin >> n;
    a = vector<lli> (n);
    for(lli i = 0;i < n;i++) cin >> a[i];
    now = a[0];c = 0;
    for(lli i = 1;i < n;i++){
        if(a[i] > 0){
            if(c){
                ans *= combination(a[i]-now+c,c);
                ans %= MOD;
                c = 0;
            }
            now = a[i];
        }
        else c++;
    }
    cout << ans << endl;
}

Submission Info

Judge Result