# include <fstream>
# define MOD 1000000007
using namespace std;
//ifstream fin("puteri3.in");
//ofstream fout("puteri3.out");
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int c[102][102],s[102],p[102],n,k,i,j,pas,x,y;
void inversModular(int a,int b,int &x,int &y){
    int xa,ya;
    if(b==0){
        x=1;
        y=0;
        return;
    }
    inversModular(b,a%b,xa,ya);
    x=ya;
    y=xa-(1LL*(a/b)*ya)%k;
    if(y<0)
        y+=k;
}
int main () {
    fin>>n>>k;
    inversModular(n,k,x,y);
    fout<<x<<"\n";
    /*s[0]=n;
    s[1]=(1LL*(n*(n+1)/2))%MOD;
    c[0][0]=1;
    p[0]=1;
    inversModular(k,MOD,x,y);
    for(i=1;i<=k+1;i++)
        p[i]=(1LL*p[i-1]*n)%MOD;
    for(i=1;i<=k;i++){
        c[i][0]=1;
        for(j=1;j<=i;j++){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            if(c[i][j]>=MOD)
                c[i][j]-=MOD;
        }
    }
    for(i=2;i<=k;i++){
        for(j=i-1,pas=1;j>=0;j--,pas++){
            if(pas%2==1)
                s[i]+=(1LL*c[k][pas+1]*s[j])%MOD;
            else
                s[i]-=(1LL*c[k][pas+1]*s[j])%MOD;
            if(s[i]>=MOD)
                s[i]-=MOD;
            if(s[i]<0)
                s[i]+=MOD;
        }
        s[i]+=p[i+1];
        if(s[i]>=MOD)
            s[i]-=MOD;
        s[i]=(1LL*s[i]*x)%MOD;
    }
    fout<<s[k]<<"\n";*/
    return 0;
}