#include <bits/stdc++.h>

using namespace std;

long long powmaibunfraiere( long long b, long long e, long long r ) {
    long long p = 1;
    while ( e ) {
        p %= r;
        if ( e % 2 )
            p = ( ( p % r ) * ( b % r ) ) % r;
        b = ( ( b % r ) * ( b % r ) ) % r;
        e /= 2;
    }
    return p;
}

long long oilarboi( long long n ) {
    long long d = 2, p, prod = n;
    while ( d * d <= n ) {
        p = 0;
        while ( n % d == 0 ) {
            n /= d;
            p ++;
        }
        if ( p )
            prod = prod / d * ( d - 1 );
        d ++;
    }
    if ( n > 1 )
        prod = prod / n * ( n - 1 );
    return prod;
}

int main() {
    long long a, n;
    ifstream fin( "inversmodular.in" );
    fin >> a >> n;
    fin.close();

    ofstream fout( "inversmodular.out" );
    fout << powmaibunfraiere( a, oilarboi( n ) - 1, n );
    fout.close();
    return 0;
}