#include <bits/stdc++.h>
#define ll long long

using namespace std;

FILE*f=fopen("inversmodular.in","r");
FILE*g=fopen("inversmodular.out","w");

ll n,a;

ll putere(ll x,ll y) {
    ll z;
    if (y==0) return 1;
    if (y==1) return x;
    z=putere(x,y/2)%n;
    if (x%2==0) return (z*z)%n;
    return ((z*z)%n*x)%n;

}

int main() {
    fscanf(f,"%lld%lld",&n,&a);
    fprintf(g,"%lld",putere(a,n-2)%n);
    return 0;
}