#include <fstream>
#include <iostream>
#include <queue>

using namespace std;
const int mod=1999999973;

int main(){
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int ans, n, a, p;
    fin>>a>>n;
    ans=1;
    p=n-2;
    while(p){
        if(p&1)
            ans=((long long)ans*a)%n;
        a=((long long)a*a)%mod;
        p>>=1;
    }
    fout<<ans;
    return 0;
}