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

using namespace std;
 
ll n,p,m=100003,a,phi;

ll pw(ll n, ll p)
{
    ll rs=1;
    while (p)
    {
        if (p&1) rs=rs*n%m;
        n=n*n%m;
        p=p>>1;
    }
    return rs;
}

ll euler(int n)
{
    ll rs=1,fact=2;
    while (n!=1)
    {
        ll k=0;
        if (n%fact==0)
        {
            while (n%fact==0) n/=fact,k++;
            rs=rs*pw(fact,k-1)*(fact-1);
        }
        fact++;
    }
    return rs;
}

bool prim(int n)
{
    for (int i=2; i<=sqrt(n); i++)
        if (n%i==0) return 0;
    return 1;
}

int main() 
{
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    cin>>a>>n;
    if (prim(n)) cout<<pw(a,n-2); else
    {
        phi=euler(n);
        cout<<pw(a,phi-1);
    }
}