• 1.1.首先x+y=n在任何时刻都恒成立。所以如果(x,n)=1那么(y,n)=1也必定成立。
• 1.2.关于gcd()，记作()，支持几种操作：(n-x,n)=(-x,n)=(x,n)也就是说，一边加到另一边，一边取反，gcd的还是不变的。可以由同余的性质证明。
• 2.1.每次符合条件k的指数就会增加，所以问题就变成了1-n里面和n互质的数，的和。
• 2.2.欧拉定理，即费马小定理的推广，介绍了欧拉函数phi(x)表示小于x的数里面，与x互质的数，的个数。有1.1得到的结论，如果x和n互质，那么n-x也和n互质。两数之和等于n。所以两两配个对。所有数之和 sum(x)=n \times φ(n) \div 2
• 2.3.关于n或phi(n)的奇偶，如果phi(n)是奇数，那么n/2就会和n互质。但由于n/2还是n的一个约数。所以n只能为2。所以phi(n)为奇数当且仅当n=2,此时也可以整除。同时证明了当n不等于2的时候phi(n)一定为偶数。
• 3.1.最后快速幂处理答案。注意模

#include
using namespace std;
typedef long long ll;
const ll mod=1000000000+7;
ll n,k,a,b;
ll ksm(ll n,ll m)
{
    ll res=1;
    while(m)
    {
        if(m&1) res=res*n %mod;
        n=n*n %mod;
        m>>=1;
    }
    return res %mod;
}
int main()
{
    cin>>n>>k>>a>>b;
    ll euler=n,bn=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0) euler=euler/i*(i-1);
        for(;n%i==0;n/=i);
    }
    if(n!=1) euler=euler/n*(n-1);
    ll p=euler/2*bn;
    ll num=a%mod +b%mod;
    cout<