Submission #1781269

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int mod = 1777777777;
struct ModCombination {
  ModCombination(unsigned int n) : n(n), F(n + 1, 1), I(n + 1, 1) {
    for (int i = 1; i <= n; ++i) F[i] = 1ll * i * F[i - 1] % mod;
    for (long long i = mod - 2, j = F[n]; i; i >>= 1) {
      if (i & 1) I[n] = I[n] * j % mod;
      j = j * j % mod;
    }
    for (int i = n - 1; i; --i) I[i] = I[i + 1] * (i + 1ll) % mod;
  }

  unsigned int n;
  vector<int> F, I;

  int operator()(int p, int k) {
    if (p > n) exit(-1);
    if (k > p) return 0;
    return 1ll * F[p] * I[k] % mod * I[p - k] % mod;
  }
};

int main() {
  long long n, k;
  cin >> n >> k;

  if (n >= mod) {
    cout << 0 << endl;
  }

  vector<long long> fact(n + 1, 1);
  for (int i = 1; i < fact.size(); ++i) {
    fact[i] *= i * fact[i - 1];
    fact[i] %= mod;
  }

  ModCombination mc(n);
  long long t = 0;
  for (int i = 0; i <= k; ++i) {
    t += (mc(k, i) * fact[k - i] % mod) * (i & 1 ? -1 : 1);
    t %= mod;
  }

  cout << mc(n, k) * t % mod << endl;
}

Submission Info

Judge Result