#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define all(a) (a).begin(), (a).end()

#define fillchar(a, x) memset(a, x, sizeof(a))

#define huan printf("\n");

#define debug(a,b) cout<<a<<" "<<b<<" ";

using namespace std;

const int maxn=1e5+,inf=0x3f3f3f3f;

typedef long long ll;

typedef pair<int,int> pii;

const ll mod=1e9+;

int yin[maxn],cnt;

void euler(ll n)  //返回euler(n)

{

    ll res=n,a=n;

    cnt=;

    for(ll i=; i*i<=a; i++)

    {

        if(a%i==)

        {

            yin[cnt++]=i;

            res=res/i*(i-);//先进行除法是为了防止中间数据的溢出 爆int

            while(a%i==)

                a/=i;

        }

    }

    if(a>)

        res=res/a*(a-),yin[cnt++]=a;

}

ll powmod(ll n,ll m)

{

    ll ans=;

    while(m>)

    {

        if(m&)

            ans=ans*n%mod;

        m = m>>;

        n = n*n%mod;

    }

    return ans;

}

ll inv2=powmod(,mod-);

ll inv6=powmod(,mod-);

ll getsum1(ll n)

{

    return n*(n+)%mod*(*n%mod+)%mod*inv6%mod;

}

ll getsum2(ll n)

{

    return n*(n+)%mod*inv2%mod;

}

int main()

{

    ll n,m;

    while(scanf("%lld%lld",&n,&m)!=EOF)

    {

        euler(m);

        ll ans=(getsum1(n)+getsum2(n))%mod;

        for(int i=; i<(<<cnt); i++)

        {

            ll temp=,jishu=;

            for(int j=; j<cnt; j++)

            {

                if(i&(<<j))

                    temp*=yin[j],jishu++;

            }

            if(temp==)continue;

            ll bei=n/temp;

            ans=(ans+powmod(-,jishu)*temp*temp%mod*getsum1(bei)%mod+mod)%mod;

            ans=(ans+powmod(-,jishu)*temp*getsum2(bei)%mod+mod)%mod;

        }

        printf("%lld\n",ans);

    }

}