Submission #1500413

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
 
int log_(long long int k){ return 63 - __builtin_clzll(k); }
long long int alter(long long int k){ return 1LL << log_(k); }
long long int pow_mod(long long int r, long long int p, long long int mod){  
  if(p <= 0){ return 1; }
  long long int ans = r;
  for(int i = 0; i < log_(p); i++){
    ans *= ans;
    ans %= mod;
  }
  ans *= pow_mod(r, p - alter(p), mod);
  ans %= mod;
  
  return ans;
}
 
int main(void){
  const int mod = (1e9) + 7;
  int n, a;
  cin >> n;
  vector<long long int> bucket(n, 0);
  for(int i = 0; i < n; i++){
    cin >> a;
    if((i == 0 && a != 0)
       || (i != 0 && (a <= 0 || n <= a))){
      cout << 0 << endl;
      return 0;
    }
    ++bucket[a];
  }
  
  long long int ans = 1;
  for(int i = 1; i < n; i++){
    if(bucket[i] != 0 && bucket[i - 1] == 0){
      cout << 0 << endl;
      return 0;
    }
      
    ans *= pow_mod(pow_mod(2, bucket[i - 1], mod) - 1, bucket[i], mod);
    ans %= mod;
    ans *= pow_mod(2, (bucket[i] * (bucket[i] - 1)) / 2, mod);
    ans %= mod;
  }
 
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result