#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll n,a,c,m,sum=1;

int main(){
    cin>>a>>m;
    for(ll i=1;i<m;i++){
        for(ll j=1;j<=m;j++){
            if((a*j+i)%m==j){
                sum*=j;
                sum%=1000000007;
            }
        }
    }
    cout<<sum;
    return 0;
}