#include "message.h"
#include "futbol.h"
#include "bits/stdc++.h"

using namespace std;

void gcdExtended(int64_t a, int64_t b, int64_t *x, int64_t *y) {
    if(a==0) {
        *x=0; *y=1;
        return;
    }
    int64_t x1,y1;

    gcdExtended(b%a, a, &x1, &y1);
    *x=y1-(b/a)*x1;
    *y=x1;
}

/**
 * Funkcja zwraca dzielnik w matematyce module dla a (1/a) przy użyciu algorytmu Euklidesa.
 */
int64_t findDiv(int64_t a, int64_t p) {
    int64_t x,y;
    gcdExtended(a, p, &x, &y);
    return ((x%p+p)%p);
}


/**
 * Zwraca 2^n % p;
 */
int64_t pow2(int n, int p) {
    int64_t res=1;
    int64_t pow=2;
    while(n>0) {
        if(n&1) res=(res*pow)%p;
        pow=(pow*pow)%p;
        n>>=1;
    }
    return res;
}


int64_t calc(int64_t n, int64_t k, int64_t p) {
    int64_t denom=1;
    int64_t res=1;
    int64_t mul=1;

    if(k==0) return 1;

    for(int64_t i=1;i<=k;++i) {
        const int64_t l=n-i+1;
        // podnośimy poprzednią wartość do wspólnego mianownika
        res=(res*i)%p;
        denom=(denom*i)%p;
        // aktualizujemy mnożnik o nowy element
        mul=(mul*l)%p;
        // Dodajemy do licznika nowy element
        res=(res+mul)%p;
    }

    int64_t d=findDiv(denom, p);
    return (res*d)%p;
}

int64_t smartCalc(int n, int k, int p) {

    if(k>n/2) {
        // suma wyrazów n-tego poziomu trójkąta pasca to 2^n
        int64_t rest=pow2(n,p);
        return (rest-calc(n, n-k-1, p)+p)%p;
    } else {
        return calc(n, k, p);
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int p=GetP(), k=GetK(), n=GetN();
    bool nKnown;
    const int lastNode=NumberOfNodes()-1;
    /** Czy główny komputer */
    const bool master=MyNodeId()==0;

//    if(k<100 || NumberOfNodes()==1) {
    if(k<1000000 || NumberOfNodes()==1) {
        if(master) {
            cout<<smartCalc(n, k, p)<<endl; // główny liczy i wypisuje
        }
        return 0;   // koniec dla wszystkich
    }

    // Czy znane jest N?
    if(master) {
        Receive(lastNode);
        nKnown=GetLL(lastNode)>0;// jeżeli jest znane, to jest jego wartość
    } else {
        nKnown=n>0;
        if(MyNodeId()==lastNode) {  // jeżeli jestem ostatni, to wysyłam do głównego informacje, czy znany jest N
            PutLL(0, n);
            Send(0);
            return 0;   // On już więcej nic nie będzie robił; tylko syngalizuje, stan
        }
    }

    // czy tryb pracy we dwóch
    bool two=false;

    if(!nKnown) {   // jeżeli nie znany, to liczymy na dwa komputery - wiadomość tam i wynik
        two=true;
        if(master) {    // główny wysyła do jednego komputera informacje
            PutLL(1, n);    // z informacją o N
            Send(1);
        } else {
            if(MyNodeId()==1) { // jeżeli jesteśmy tym drugim, to czekamy na N
                Receive(0); // z mastera odbieramy
                n=(int)GetLL(0);  // N
            } else {
                return 0;   // pozostali kończą
            }
        }
    }

    /** Czyli liczymy drugą połowę */
    bool invert=false;
    if(k>n/2) {
        k=n-k-1; invert=true;
    }

    // jeżeli N jest znane i k jest całkiem spore, to liczymy równolegle
    const int nodes=two?2:(NumberOfNodes()-1);  // bez jednego, bo posłużył jako test dla N
    // Rozmiar danych dla jednego komputera
    const int part=(k+nodes-1)/nodes;

    // zakres od
    const int from=part*MyNodeId()+1;
    // zakres do
    const int to=min(from+part-1, k);

    // liczymy swoją część (n from) + (n from+1) + ... + (n to)
    /// licznik
    int64_t a=1;
    /// mianiownik
    int64_t b=1;
    /// licznik sumy dla wszystkich poprzenich wyrazów
    int64_t res=0;

    for(int i=from;i<=to;++i) {
        const int64_t l=n-i+1;
        // aktualizujemy dzielnik
        b=(b*i)%p;
        // podnośimy poprzednią wartość do wspólnego mianownika (b)
        res=(res*i)%p;
        // aktualizujemy mnożnik o nowy element
        a=(a*l)%p;
        /** Dodajemy do licznika nowy element */
        res=(res+a)%p;
    }

    // try prawy wielu komputerów
    if(!two) {
        // mamy obliczoną swoją część i teraz przesyłamy dalej
        const bool lastCalcNode=MyNodeId()==nodes-1;

        if (!master) {   // jeżeli nie główny, to czekamy na pomocnicze dane
            const int prevNode = MyNodeId() - 1;
            Receive(prevNode);
            int64_t prevSum = GetLL(prevNode);
            int64_t prevA = GetLL(prevNode);
            int64_t prevB = GetLL(prevNode);
            // jak już mamy dane, to należy zaktualizować swoje wyniki
            prevSum = (prevSum * b) % p;  // aktualizujemy licznik, dla nowego dzielnika
            res = (res * prevA) % p;    // aktualizujemy licznik o brakujący mnożnik
            b = (b * prevB) % p;
            a = (a * prevA) % p;

            res = (res + prevSum) % p;    // dodajemy wartości skoro się juz zgadzają
        }

        if (!lastCalcNode) { // jeżeli nie jesteśmy ostatni, to przesyłamy dalej wynik
            const int nextNode = MyNodeId() + 1;
            PutLL(nextNode, res);
            PutLL(nextNode, a);
            PutLL(nextNode, b);
            Send(nextNode);
            return 0;
        }
    } else {    // tryb pracy dwóch komputerów
        if(!master) {    // wysyłamy swoją część danych do master-a
            PutLL(0, res);
            PutLL(0, a);
            PutLL(0, b);
            Send(0);
            return 0;   // master dokońcy
        }
        // Pobranie danych z pomocnika i obliczenie wyniku
        Receive(1);
        int64_t nextSum=GetLL(1);
        int64_t nextA=GetLL(1);
        int64_t nextB=GetLL(1);

        res=(res*nextB)%p;  // aktualizujemy licznik dla nowego mianownika
        nextSum=(nextSum*a)%p;  // aktualizujemy licznik danych od pomocnika o brakujące dane w liczniku
        b=(b*nextB)%p;

        res=(res+nextSum)%p;    // dodajemy jak już zgadzają się liczniki

    }
    // jak ostatni, to liczymy wynik
    const int64_t div = findDiv(b, p);
    int64_t val = ((res * div) % p);
    val = (val + 1) % p;  // jeszcze pusty mecz
    if (invert) {
        int64_t rest = pow2(n, p);
        val = (rest - val + p) % p;
    }
    cout << val << endl;

    return 0;
}