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
#include "message.h"
#include "futbol.h"
#define _USE_MATH_DEFINES/////////////////////////////////////////////////////
#include <bits/stdc++.h>//////////////////////////////////////////////////////
#ifdef LOC////////////////////////////////////////////////////////////////////
#include "debuglib.h"/////////////////////////////////////////////////////////
#else/////////////////////////////////////////////////////////////////////////
#define deb(...)//////////////////////////////////////////////////////////////
#define DBP(...)//////////////////////////////////////////////////////////////
#endif////////////////////////////////////////////////////////////////////////
#define x first///////////////////////////////////////////////////////////////
#define y second//////////////////////////////////////////////////////////////
#define mp make_pair//////////////////////////////////////////////////////////
#define pb push_back//////////////////////////////////////////////////////////
#define sz(x)int((x).size())//////////////////////////////////////////////////
#define each(a,x)for(auto&a:(x))//////////////////////////////////////////////
#define all(x)(x).begin(),(x).end()///////////////////////////////////////////
#define rep(i,b,e)for(int i=(b);i<(e);i++)////////////////////////////////////
using namespace std;using namespace rel_ops;using ll=int64_t;using Pii=pair///
<int,int>;using ull=uint64_t;using Vi=vector<int>;void run();int main(){cin.//
sync_with_stdio(0);cin.tie(0);cout<<fixed<<setprecision(20);run();return 0;}//
//--------------------------------------------------------------------------//

int nNodes, nodeID, k, mod;
int blockBegin, blockEnd, blockSize;

vector<pair<int, Pii>> f;
Pii g;

int modPow(ll m, int e) {
	ll t = 1;
	while (e) {
		if (e & 1) t = t*m % mod;
		e >>= 1; m = m*m % mod;
	}
	return int(t);
}

int modInv(int a) {
	int u = a, v = mod, x1 = 1, x2 = 0;

	while (u > 1) {
		int q = v/u;
		int r = v - q*u;
		int x = x2 - q*x1;
		v = u; u = r;
		x2 = x1; x1 = x;
	}

	if (x1 < 0) x1 += mod;
	return x1;
}

int eval(pair<int, Pii> p, int baseF, int baseG) {
	ll y = ll(p.y.x)*modInv(p.y.y) % mod;
	return int((ll(p.x)*baseF + y*baseG) % mod);
}

void precompute() {
	f.resize(blockSize+1);
	f[0] = { 1, {0, 1} };
	g = {1, 1};

	rep(i, 1, sz(f)) {
		Pii sec = f[i-1].y;
		f[i].x = f[i-1].x*2 % mod;
		f[i].y.y = int(ll(sec.y)*g.y % mod);
		f[i].y.x = int((ll(sec.x)*g.y*2 - ll(sec.y)*g.x) % mod);
		if (f[i].y.x < 0) f[i].y.x += mod;

		int n = blockBegin+i;
		g.x = int((ll(g.x) * n) % mod);
		g.y = int((ll(g.y) * (n-k)) % mod);
	}
}

void solve() {
	int n, baseF, baseG;

	if (nodeID == 0) {
		n = GetN();
		baseF = modPow(2, k);
		baseG = 1;
	} else {
		Receive(nodeID-1);
		n = GetInt(nodeID-1);
		baseF = GetInt(nodeID-1);
		baseG = GetInt(nodeID-1);
	}

	if (n >= blockBegin && n < blockEnd) {
		cout << eval(f[n-blockBegin], baseF, baseG) << endl;
	}

	if (nodeID+1 < nNodes) {
		int nextF = eval(f.back(), baseF, baseG);
		ll tmp = ll(g.x)*modInv(g.y) % mod;
		int nextG = int(tmp*baseG % mod);

		PutInt(nodeID+1, n);
		PutInt(nodeID+1, nextF);
		PutInt(nodeID+1, nextG);
		Send(nodeID+1);
	}
}

void run() {
	nNodes = NumberOfNodes();
	nodeID = MyNodeId();
	k = GetK();
	mod = GetP();

	int per = (mod-k+nNodes-1) / nNodes;
	blockBegin = min(mod, k + per*nodeID);
	blockEnd = min(mod, blockBegin + per);
	blockSize = blockEnd-blockBegin;

	precompute();
	solve();
}