Submission #1165218

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

#define MAX 2010

ll mod = 1000000007;

long long extgcd(long long a,long long b,long long& x,long long& y) {
  long long d = a;
  if(b != 0) {
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }
  else x = 1,y = 0;
  return d;
}

long long mod_inv(long long a,long long m) {
  long long x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}

int N,A[MAX];

void compute() {
  vector<int> vec,num;
  rep(i,N) if( A[i] != -1 ) {
    vec.push_back(A[i]);
    int cur = i + 1;
    while( cur < N && A[cur] == -1 ) ++cur;
    num.push_back(cur-i-1);
  }
  long long ans = 1;
  rep(i,(int)vec.size()-1) {
    int a = vec[i+1] - vec[i];
    int b = num[i];
    long long denom = 1, numer = 1;
    REP(j,1,b+1) {
      ( denom *= ( (ll)( a + b - ( j - 1 ) ) % mod ) ) %= mod;
      ( numer *= (ll)j ) %= mod;
    }
    ( ans *= ( ( denom * mod_inv(numer,mod) ) % mod ) ) %= mod;
  }
  cout << ans << endl;
}

int main() {
  cin >> N;
  rep(i,N) cin >> A[i];
  compute();
  return 0;
}

Submission Info

Judge Result