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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
#include "message.h"
#include "futbol.h"
using namespace std;

using ll = long long;

ll inverse(ll a, ll mod) {
  return a == 1 ? 1 : ((a-inverse(mod % a, a))*mod+1)/a;
}

ll pow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n) {
    if (n % 2) {
      res = res * a % mod;
    }
    a = a * a % mod;
    n /= 2;
  }
  return res;
}

ll nodes;
ll id;

ll n, k, p;

int main() {
  nodes = NumberOfNodes();
  id = MyNodeId();
  k = GetK();
  p = GetP();
  const ll range = (p - k) / nodes + 1;
  const ll b = min(k + id * range, p - 1);
  // const ll e = min(b + range, p) - 1; // FIXME
  const ll e = min(b + range, p - 1);
  // if (id) return 0;
  // cerr << '(' << b << ", " << e  << ']' << endl;

  auto calc_T = [](ll b, ll e) {
    ll Tsum = 1;
    ll twoinv = inverse(2, p);
    ll twopow = 1;
    ll one = 1;
    for (ll i = e - 1; i > b; i--) {
      twopow = twopow * 2 % p;
      Tsum = Tsum * twoinv % p;
      Tsum = Tsum * i % p;
      one = one * (i - k) % p;
      Tsum = (Tsum + one) % p;
    }
    Tsum = Tsum * inverse(one, p) % p;
    Tsum = Tsum * twopow % p;
    return Tsum;
  };

  ll Tsum = calc_T(b, e);

  ll ek = [b, e]() {
    ll res = 1, den = 1;
    for (ll i = b + 1; i <= e; i++) {
      res = res * i % p;
      den = den * (i - k) % p;
    }
    return res * inverse(den, p) % p;
  }();
  // cerr << "Tsum " << Tsum << endl;

  ll bk, prevT;
  if (id == 0) {
    n = GetN();
    prevT = pow(2, k, p);
    bk = 1;
  } else {
    Receive(id-1);
    n = GetInt(id-1);
    prevT = GetInt(id-1);
    bk = GetInt(id-1);
  }
  // cerr << prevT << endl;
  ll Tres = pow(2, e-b, p) * prevT % p - (bk * Tsum) % p;
  if (Tres < 0) {
    Tres += p;
  }
  ek = ek * bk % p;
  if (id + 1 < nodes) {
    PutInt(id+1, n);
    PutInt(id+1, Tres);
    PutInt(id+1, ek);
    Send(id+1);
  }
  // cerr << ek << ' ' << Tres << endl;

  if (n == k && id == 0) {
    cout << prevT << endl;
    return 0;
  }
  if (!(b < n && n <= e)) {
    return 0;
  }
  Tsum = calc_T(b, n);
  Tres = pow(2, n-b, p) * prevT % p - (bk * Tsum) % p;
  if (Tres < 0) {
    Tres += p;
  }
  cout << Tres << endl;
}