//2500186
//Sreejata Kishor Bhattacharya
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
long long int modul(long long int n, long long int m){
long long int t=1;
for (int i=0; i<n; i++){
t= t*2;
t=t%m;
}
return t;
}
long long int f[150000], g[150000];
int main() {
long long int n, m, j;
cin>>n;
cin>>m;
float t= sqrt(n);
t= floor(t);
j= (long long int) t;
long long int ir= 0;
for (int i=1; i<=j; i++){
if (n%i==0){
if (i!=n/i){
f[ir]= i;
f[ir+1]= n/i;
ir+=2;
}
else {
f[ir]= i;
ir+=1;
}
}
}
sort(f, f+ir);
/*
map <int, int> t;
t[1]= 2%m;
for (int i=0; i<150001; i++){
t[i+1]= 2*t[i];
t[i+1]= t[i+1]%m;
}
*/
map <int, int> tu;
tu[1]= 2%m;
for (int i=1; i<150001; i++){
tu[i+1]= 2*tu[i];
tu[i+1]= tu[i+1]%m;
}
g[0]= modul(1, m);
for (int i=1; i<ir; i++){
/*
int sum= 0, t= t[f[i]];
*/
int sum= 0, t= tu[f[i]];
for (int t=0; t<i; t++){
if (f[i]%f[t]==0){
sum+=g[t]%m;
}
sum= sum%m;
}
g[i]= t-sum;
// g[i]= g[i]%m;
g[i]= g[i]%m;
if (g[i]<0){
g[i]= m+g[i];
g[i]= g[i]%m;
}
// (didn't include the if(g[i]<0) part in my original submission
}
cout<<g[ir-1]<<endl;
return 0;
}
Ly8yNTAwMTg2Ci8vU3JlZWphdGEgS2lzaG9yIEJoYXR0YWNoYXJ5YQojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxtYXA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmxvbmcgbG9uZyBpbnQgbW9kdWwobG9uZyBsb25nIGludCBuLCBsb25nIGxvbmcgaW50IG0pewogICAgbG9uZyBsb25nIGludCB0PTE7CiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKXsKICAgICAgICB0PSB0KjI7CiAgICAgICAgdD10JW07CiAgICB9CiAgICByZXR1cm4gdDsKfQoKbG9uZyBsb25nIGludCBmWzE1MDAwMF0sIGdbMTUwMDAwXTsKCmludCBtYWluKCkgewogICAgbG9uZyBsb25nIGludCBuLCBtLCBqOwogICAgY2luPj5uOwogICAgY2luPj5tOwogICAgZmxvYXQgdD0gc3FydChuKTsKICAgIHQ9IGZsb29yKHQpOwogICAgaj0gKGxvbmcgbG9uZyBpbnQpIHQ7CgogICAgbG9uZyBsb25nIGludCBpcj0gMDsKCiAgICBmb3IgKGludCBpPTE7IGk8PWo7IGkrKyl7CiAgICAgICAgaWYgKG4laT09MCl7CiAgICAgICAgICAgIGlmIChpIT1uL2kpewogICAgICAgICAgICBmW2lyXT0gaTsKICAgICAgICAgICAgZltpcisxXT0gbi9pOwogICAgICAgICAgICAgICBpcis9MjsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGZbaXJdPSBpOwogICAgICAgICAgICAgICAgaXIrPTE7CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgfQogICAgc29ydChmLCBmK2lyKTsKCi8qCiAgICBtYXAgPGludCwgaW50PiB0OwogICAgdFsxXT0gMiVtOwogICAgZm9yIChpbnQgaT0wOyBpPDE1MDAwMTsgaSsrKXsKICAgICAgICB0W2krMV09IDIqdFtpXTsKICAgICAgICB0W2krMV09IHRbaSsxXSVtOwogICAgfQoqLwogICAgbWFwIDxpbnQsIGludD4gdHU7CiAgICB0dVsxXT0gMiVtOwogICAgZm9yIChpbnQgaT0xOyBpPDE1MDAwMTsgaSsrKXsKICAgICAgICB0dVtpKzFdPSAyKnR1W2ldOwogICAgICAgIHR1W2krMV09IHR1W2krMV0lbTsKICAgIH0KICAgIGdbMF09IG1vZHVsKDEsIG0pOwogICAgZm9yIChpbnQgaT0xOyBpPGlyOyBpKyspewovKgogICAgICAgIGludCBzdW09IDAsIHQ9IHRbZltpXV07CiovCiAgICAgICAgaW50IHN1bT0gMCwgdD0gdHVbZltpXV07CiAgICAgICAgZm9yIChpbnQgdD0wOyB0PGk7IHQrKyl7CiAgICAgICAgICAgIGlmIChmW2ldJWZbdF09PTApewogICAgICAgICAgICAgICAgc3VtKz1nW3RdJW07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgc3VtPSBzdW0lbTsKCiAgICAgICAgfQogICAgICAgIGdbaV09IHQtc3VtOwogICAgIC8vIGdbaV09IGdbaV0lbTsKICAgICAgIGdbaV09IGdbaV0lbTsgIAogICAgICAgIGlmIChnW2ldPDApewogICAgICAgIAlnW2ldPSBtK2dbaV07CiAgICAgICAgCWdbaV09IGdbaV0lbTsKICAgICAgICB9CiAgICAgICAvLyAoZGlkbid0IGluY2x1ZGUgdGhlIGlmKGdbaV08MCkgcGFydCBpbiBteSBvcmlnaW5hbCBzdWJtaXNzaW9uIAoKICAgIH0KCQogICAgY291dDw8Z1tpci0xXTw8ZW5kbDsKCgogICAgcmV0dXJuIDA7Cn0K