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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include "message.h"
#include "futbol.h"
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto &i : a)
#define SZ(i) ((int)(i).size())
#define X first
#define Y second
#define PR std::pair
#define PII std::pair<int, int>
#define MP std::make_pair
#define ll long long
#define VI std::vector<int>

int modpow(int b, int e, int mod){
	int ret = 1;
	b = b%mod;
	while(e > 0){
		if(e % 2 == 1) ret = (1ll*ret*b)%mod;
		e >>= 1;
		b = (1ll*b*b)%mod;
	}
	return ret;
}

int mul_inv(int a, int b)
{
	int b0 = b, t, q;
	int x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

int n, k, p;
int NODES, ME;
std::vector<PII> przedz;

int main(){
	NODES = NumberOfNodes();
	ME = MyNodeId();
	n = GetN();
	k = GetK();
	p = GetP();
	bool swapped = false;

	if(n == 0){
		if(ME == 1){
			PutInt(0, -2137);
			Send(0);
		}
		return 0;
	}

	if(k > n/2) k = n - k - 1, swapped = true;

	if(k < NODES){
		if(ME != 0) return 0;
		int ans = 0;
		if(k >= 0) ans++;
		if(k > 0){
			int up = 1;
			int down = 1;
			REP(i, 1, k+1){
				up = (1ll*up*(n-i+1))%p;
				down = (1ll*down*i)%p;
				// ans = (1ll*ans+1ll*up*modpow(down, p-2, p))%p;
				ans = (1ll*ans+1ll*up*mul_inv(down, p))%p;
			}
		}
		if(swapped){
			ans = modpow(2, n, p) - ans;
			if(ans < 0) ans += p;
		}
		std::printf("%d", ans);
		return 0;
	}

	// remember to add 1 to answer
	int place = 1;
	FOR(i, NODES){
		int upto = (i < NODES-1 ? place+(k+1)/NODES : k+1);
		przedz.push_back(MP(place, upto-1));
		place = upto;
	}
	std::reverse(przedz.begin(), przedz.end());

	int ans = 0;

	int up = 1;
	int down = 1;

	REP(i, przedz[ME].X, przedz[ME].Y+1){
		up = (1ll*up*(n-i+1))%p;
		down = (1ll*down*i)%p;
		// ans = (1ll*ans+1ll*up*modpow(down, p-2, p))%p;
		ans = (1ll*ans+1ll*up*mul_inv(down, p))%p;
	}

	if(ME != NODES-1){
		Receive(ME+1);
		int lup = GetInt(ME+1);
		if(ME == 0 && lup == -2137){
			ans = 0;
			if(k >= 0) ans++;
			if(k > 0){
				up = 1;
				down = 1;
				REP(i, 1, k+1){
					up = (1ll*up*(n-i+1))%p;
					down = (1ll*down*i)%p;
					// ans = (1ll*ans+1ll*up*modpow(down, p-2, p))%p;
					ans = (1ll*ans+1ll*up*mul_inv(down, p))%p;
				}
			}
			if(swapped){
				ans = modpow(2, n, p) - ans;
				if(ans < 0) ans += p;
			}
			std::printf("%d", ans);
			return 0;
		}
		int ldown = GetInt(ME+1);
		int lans = GetInt(ME+1);
		ans = (1ll*ans*lup)%p;
		ans = (1ll*ans*modpow(ldown, p-2, p))%p;
		up = (1ll*up*lup)%p;
		down = (1ll*down*ldown)%p;
		ans = (1ll*ans+lans)%p;
	}

	if(ME != 0){
		PutInt(ME-1, up);
		PutInt(ME-1, down);
		PutInt(ME-1, ans);
		Send(ME-1);
	}

	if(ME == 0){
		ans++;
		if(swapped){
			ans = modpow(2, n, p) - ans;
			if(ans < 0) ans += p;	
		}
		std::printf("%d", ans);
	}

	return 0;
}