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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>

#include "message.h"
#include "futbol.h"

#define ll long long

ll p;

ll pow(ll a, ll b) {
  ll x = 1;
  a %= p;
  while(b > 0) {
    if((b&1)!=0) {
      x *= a;
      x %= p;
    }
    b >>= 1;
    a *= a;
    a %= p;
  }
  return x;
}

ll div(ll a, ll b) {
  return (a*pow(b,p-2))%p;
}

int* inv;

void makeInv() {
  inv = new int[p+5];
  inv[1] = 1;
  for(int i=2;i<p;i++) {
    inv[i] = (p - ((p/i)*inv[p%i] % p)) % p;
  }
}

int main(int argc, char** argv) {
  int me = MyNodeId();
  if(me == 0) {
    ll n = GetN();
    ll k = GetK();
    if(k > n/2) {
      k = n-k;
    }
    p = GetP();
    ll res = 1;
    ll num = 1;
    ll den = 1;
    if(p < 14000000) {
      makeInv();
      for(ll i=1;i<=k;i++) {
        num *= n+1-i;
        num %= p;
        den *= i;
        den %= p;
        ll a = num * inv[den];
        a %= p;
        res += a;
        res %= p;
      }
    } else {
     for(ll i=1;i<=k;i++) {
        num *= n+1-i;
        num %= p;
        den *= i;
        den %= p;
        res += div(num,den);
        res %= p;
      }
    }

    printf("%lld\n", res);
  }
  return 0;
}