1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "message.h"
#include "futbol.h"

#include <algorithm>
#include <cstdio>

using LL = long long;

std::pair<LL, LL> extended_gcd(LL a, LL b)
{
  LL s = 0, old_s = 1,
  t = 1, old_t = 0,
  r = b, old_r = a;

  while (r != 0) {
    LL quotient = old_r / r;

    std::swap(r, old_r -= quotient * r);
    std::swap(s, old_s -= quotient * s);
    std::swap(t, old_t -= quotient * t);
  }

  return { old_s, old_t };
}

#define MOD_INV(a, N) ((extended_gcd(a, N).first + (N)) % (N))

int main()
{
  if (MyNodeId() != 0) return 0;

  LL n = GetN(), k = GetK(), p = GetP();
  //k = std::min(k, n - k);

  LL res = 1, a = n, b = 1;
  for (LL i = 1; i <= k; i++) {
    res = (res + a * MOD_INV(b, p) % p) % p;
    a = a * (n - i) % p;
    b = b * (i + 1) % p;
  }

  std::printf("%lld\n", res);
}