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 <iostream>
#include "message.h"
#include "futbol.h"
#define ull long long int
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORI(i,start,n) for(int i=(start);i<(n);++i)
#define FORit(it,collection) for(auto it = collection.cbegin(); it != collection.cend(); it++)
#include<map>
#define DEBUG 0
#define dcout DEBUG && cout
using namespace std;
//int GetN(){return MyNodeId()==0?999999936:0;}int GetK(){return 999999935;}int GetP(){return 999999937;}
pair<int,int> extendedEuclidian(int a, int b) {
    if(b==0) {
        return pair<int,int>(1, 0);
    }
    pair<int,int> p = extendedEuclidian(b, a % b);
    return pair<int,int>(p.second, p.first - a / b * p.second);
}
// beszczelnie skopiowane z https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
int modInverse(int a, int m) 
{ 
    int m0 = m; 
    int y = 0, x = 1; 
  
    if (m == 1) 
      return 0; 
  
    while (a > 1) 
    { 
        // q is quotient 
        int q = a / m; 
        int t = m; 
  
        // m is remainder now, process same as 
        // Euclid's algo 
        m = a % m, a = t; 
        t = y; 
  
        // Update y and x 
        y = x - q * y; 
        x = t; 
    } 
  
    // Make x positive 
    if (x < 0) 
       x += m0; 
  
    return x; 
} 
ull rev(int P, int m){ return modInverse(m,P);
    ull tmp=(P+extendedEuclidian(P,m).second)%P;
    if(tmp<=0)cout<<"zero!";
    return tmp;
}

int main(){
    ull N=GetN();
    int K=GetK();
    int P=GetP();
    
    ull s=0;
    ull g=1;
    
    int nodes  = NumberOfNodes();
    int node = MyNodeId();
    
    if(K<1e6){
        if(node==0){
            for(int k=N,i=1;i<=K;--k,++i){
                ull r=rev(P,i);
                g=((g*k)%P*r)%P;
                //dcout<<"k: "<<k<<"; g: "<<g<<"; r: "<<r<<"; i: "<<i<<endl;
                s=(s+g)%P;
            }
            ++s;
            cout<<s<<endl;
        }
        return 0;
    }
    
    if(node==0){
        FOR(i,nodes-1){PutInt(i+1,N);Send(i+1);}
        ull*sums=new ull[nodes];
        ull*words=new ull[nodes];
        FOR(i,nodes-1){Receive(i+1);sums[i]=GetLL(i+1);words[i]=GetLL(i+1);}
        s=sums[nodes-1-1]%P;
        for(int i=nodes-1-1-1;i>=0;--i){
            s=(sums[i]+words[i]*s)%P;
        }
        ++s;
        if(K==N)++s;
        cout<<s<<endl;
        return 0;
    }
    
    Receive(0);
    N=GetInt(0);
    --nodes;
    --node;
    
    int wordsToCalculate=min(K,((int)N)/2);//dcout<<"will compute "<<wordsToCalculate<<endl;
    int doubleWordsStart=N-K;//dcout<<"will double after "<<doubleWordsStart<<endl;
    int wordsPerNode=wordsToCalculate/nodes+100;//dcout<<"per node "<<wordsPerNode<<endl;
    int startWord=node*wordsPerNode;//dcout<<"will start "<<startWord<<endl;
    int endWord=min(startWord+wordsPerNode,wordsToCalculate);//dcout<<"will end "<<endWord<<endl;
    
    int n = N - startWord;
    for(int i=startWord+1;i<=endWord;++i){
        ull r=rev(P,i);
        g=((g*n)%P*r)%P;
        s=(s+g)%P;
        if(i>=doubleWordsStart && i+1!=n){s=(s+g)%P;}
        --n;
    }
    PutLL(0,s);
    PutLL(0,g);
    Send(0);
    return 0;
}