#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ( "inversmodular.in" );
ofstream fout ( "inversmodular.out" );

int main () {
    
    long long a, p, d, cp, x, phi = 1, e;
    
    fin >> a >> p;
    
    cp = p;
    
    d = 2;
    while ( d * d <= p ){
        
        e = 1;
        
        while ( p % d == 0 ){
            e = e * d;
            p = p / d;
        }
        
        if ( e > 1 )
            phi = phi * ( e / d ) * ( d - 1 );
        
        d++;
    }
    
    if ( p > 1 )
        phi = phi * ( p - 1 );
    
    x = 1;
    phi--;
    while ( phi > 0 ) {
        
        if ( phi % 2 == 1 )
            x = x * a % cp;
            
        a = a * a % cp;
        phi = phi / 2;
    }
    
    fout << x;
    
    return 0;
}