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
#include "message.h"
#include "futbol.h"
#include <bits/stdc++.h>
using namespace std;

long long MOD;
long long M;
long long N, K;
const long long MAX = 100000004;
long long WW[103];
long long TT[103];

long long potega(long long a, long long pow){
	if(pow == 0){
		return 1;
	} else if(pow == 1){
		return a % MOD;
	}
	long long w = potega(a, pow/2);
	w *= w;
	w %= MOD;
	if(pow % 2 == 1){
		w *= a;
		w %= MOD;
	}
	return w;
}

long long inv(long long x){
	return potega(x, MOD - 2);
}

long long a, b;

void przedzial(long long numer){
	a = ((MAX - K) * (numer - 1))/M + K;
	b = ((MAX - K) * numer)/M + K;
	// [a, b)
}

int main(){
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(NULL);
	N = GetN();
	MOD = GetP();
	K = GetK();
	M = NumberOfNodes();
	if(MyNodeId() != 0){
		int numer = MyNodeId();
		przedzial(numer);
  		long long W = 1;
  		long long X = b - a;
  		long long T = 1;
  		long long h;
  		for(int i = 0; i < X; i++){
  			h = inv(a - K + i + 1);
  			h *= (a + i + 1);
  			h %= MOD;
  			T *= h;
  			T %= MOD;
  			if(i != X - 1){
  				W *= 2;
  				W += T;
  				W %= MOD;
  			}
  		}
  		if(X == 0){
  			W = 0;
  		}
  		long long KOD = MOD * T + W;
  		PutLL(0, KOD);
  		//PutLL(0, T);
  		//PutLL(0, W);
  		Send(0);
	} else {
		long long r;
		for(int i = 1; i < M; i++){
			Receive(i);
			r = GetLL(i);
			TT[i] = r / MOD;
			WW[i] = r % MOD;
		}
		//for(int i = 1; i < M; i++){
		//	TT[i] = GetLL(i);
		//	WW[i] = GetLL(i);
		//}
		long long obecne = potega(2, K);
		long long dwumian = 1;
		int q = 1;
		while(true){
			przedzial(q);
			if(N < b){
				break;
			}
  			long long X = b - a;
			obecne *= potega(2, X);
			obecne -= WW[q] * dwumian;
			obecne %= MOD;
			if(obecne < 0){
				obecne += MOD;
			}
			dwumian *= TT[q];
			dwumian %= MOD;
			q++;
		}
		q--;
		przedzial(q);
		// teraz robie to od b do N.
  		long long h;
		for(int i = b; i < N; i++){
			obecne *= 2;
			obecne %= MOD;
  			obecne -= dwumian;
  			if(obecne < 0){
  				obecne += MOD;
  			}
  			h = inv(i + 1 - K);
  			h *= i + 1;
  			h %= MOD;
  			dwumian *= h;
  			dwumian %= MOD;
		}
		cout << obecne << endl;
	}
}