Submission #1781327

---

Source Code Expand

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

ostream &operator<<(ostream &os, __int128_t value) {
  if (ostream::sentry(os)) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[64];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    __int128_t len = end(buffer) - d;
    if (os.rdbuf()->sputn(d, len) != len) {
      os.setstate(ios_base::badbit);
    }
  }
  return os;
}

istream &operator>>(istream &is, __int128_t &value) {
  string in;
  is >> in;
  value = 0;
  for (const char &c : in) {
    if ('0' <= c && c <= '9') value = 10 * value + (c - '0');
  }
  if (in[0] == '-') value *= -1;
  return is;
}

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

  __int128_t n;
  vector<int> F, I;

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

__int128_t mod_pow(__int128_t a, __int128_t x, __int128_t p = 1e9 + 7) {
  __int128_t ret = 1;
  for (__int128_t i = 1ll << 60; i; i >>= 1) {
    ret *= ret;
    ret %= p;
    if (x & i) {
      ret *= a;
      ret %= p;
    }
  }

  return ret;
}

__int128_t inv(__int128_t n, __int128_t p = 1e9 + 7) {
  return mod_pow(n, p - 2, p);
}

signed main() {
  __int128_t n, k;
  cin >> n >> k;

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

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

  __int128_t a = 1;
  for (__int128_t i = 0; i < k; ++i) {
    a *= n - i;
    a %= mod;
  }

  a *= inv(fact[k], mod);
  a %= mod;

  cout << a * t % mod << endl;
}

Submission Info

Judge Result