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
#include <iostream>
#include <vector>

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

using namespace std;

unsigned long long solve(int n, int k, int p) {
  vector<unsigned long long> v[2];
  v[0].resize(k + 1);
  v[1].resize(k + 1);

  v[0][0] = 1;
  for(int i = 1; i <= n; ++i) {
    v[i % 2][0] = 1;
    if(i <= k) {
      v[i % 2][i] = 1;
      for(int j = 1; j < i; ++j) {
        v[i % 2][j] = (v[(i - 1) % 2][j - 1] + v[(i - 1) % 2][j]) % p;
      }
    } else {
      for(int j = 1; j <= k; ++j) {
        v[i % 2][j] = (v[(i - 1) % 2][j - 1] + v[(i - 1) % 2][j]) % p;
      }
    }
  }

  unsigned long long res = 0;
  for(int i = 0; i <= k; ++i) {
    res = (res + v[n % 2][i]) % p;
  }

  return res;
}

int main(int argc, char const *argv[]) {

  if(MyNodeId() != 0) return 0;
  int n = GetN(), k = GetK(), p = GetP();
  cout << solve(n, k, p) << endl;

  return 0;
}