#include <stdio.h>
#include <stdlib.h>


void euclid_extins( int a, int b, long long *x, long long *y )
{
    if( b == 0 )
    {
        *x = 1;
        *y = 0;
    }
    else
    {
        long long xx, yy;
        euclid_extins( b, a % b, &xx, &yy );
        *x = yy;
        *y = xx - ( a / b ) * yy;
    }
}



int main()
{
    FILE *fin, *fout;
    int a, n;
    long long x, y;

    fin = fopen( "inversmodular.in", "r" );
    fscanf( fin, "%d%d", &a, &n );
    fclose( fin );

    euclid_extins( a, n, &x, &y );

    fout = fopen( "inversmodular.out", "w" );
    fprintf( fout, "%lld", ( ( x % n ) + n ) % n );
    fclose( fout );
    return 0;
}