Submission #1635125

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

ll modPow(ll x, ll n) {
  if (n == 0) return 1;
  ll res = modPow(x * x % mod, n >> 1);
  if (n & 1) res = res * x % mod;
  return res;
}

int main(void) {
  int n;
  cin >> n;

  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  if (a[0] != 0) {
    cout << 0 << endl;
  } else {
    vector<ll> cnt(n, 0LL);
    ll lim = 0;
    for (int i = 0; i < n; i++) {
      cnt[a[i]]++;
      lim = max(lim, a[i]);
    }

    if (cnt[0] > 1) {
      cout << 0 << endl;
    } else {
      ll ans = 1;
      for (ll i = 1; i <= lim; i++) {
        ll p = (modPow(2, cnt[i - 1]) + mod - 1) % mod;
        ans *= modPow(p, cnt[i]);
        ans %= mod;
        ans *= modPow(2, cnt[i] * (cnt[i] - 1) / 2);
        ans %= mod;
      }
      cout << ans << endl;
    }
  }

  return 0;
}

Submission Info

Judge Result