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


typedef long long ll;

struct Res{
   ll d,x,y;
};

//Wprowadzenie do algorytmów - Cormen, ... 
Res extended_euclid(ll a, ll b){
   if(b == 0)
      return {a,1,0};
   else{
      Res pom = extended_euclid(b, a%b);
      return {pom.d, pom.y, pom.x-(a/b)*pom.y};
   }
}

ll odwr(ll a, ll q){
   Res pom = extended_euclid(a,q);
   while(pom.x<0){
      pom.x += q;
   }
   return pom.x;
}

int main(){
   ll n = GetN(), k = GetK(), p = GetP();
   int Nd=NumberOfNodes(),Id=MyNodeId();
   ll prod,sum = 0,silnia = 1;
   if(n==0){
      PutLL(0,0);
      Send(0);
      return 0;
   }
   ll bound = n*(Id+1)/Nd;
   for(int i=n*Id/Nd+1; i <= bound; i++){
      silnia *= i;
      silnia %= p;
   }
   bound = (k+1)*(Id+1)/Nd;
   for(int i=(k+1)*Id/Nd; i < bound; i++){
      prod=1;
      for(int j=i+1;j<=n;j++){
         prod *= j;
         prod %= p;
      }
      for(int j=n-i+1;j<=n;j++){
         prod *= j;
         prod %= p;
      }
      sum += prod;
      sum %= p;
   }
   if(Id > 0){
      PutLL(0, silnia);
      PutLL(0, sum);
      Send(0);
   }else{
      bool par = true;
      for(int i=1;i<Nd;i++){
         Receive(i);
         prod = GetLL(i);
         //fprintf(stderr, "Rec (%d) %lld",i,prod);
         if(prod == 0 || !par){
            par = false;
            continue;  
         }   
         silnia *= prod;
         silnia %= p;
         sum += GetLL(i);
         sum %= p;
         //fprintf(stderr, " suma %lld silnia %lld\n",sum,silnia);
      }
      if(!par){
         for(int i=(k+1)/Nd;i<=k;i++){
            prod=1;
            for(int j=i+1;j<=n;j++){
               prod *= j;
               prod %= p;
            }
            for(int j=n-i+1;j<=n;j++){
               prod *= j;
               prod %= p;
            }
            sum += prod;
            sum %= p;
         }

         for(int i=n/Nd+1;i<=n;i++){
            silnia *= i; 
            silnia %= p;
         }
      }

      silnia = odwr(silnia, p);

      printf("%lld", (silnia*sum)%p);
   }

}