小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。
游戏规则是这样的：
假设道路长度为米(左端点为，右端点为)，同时给出一个数(下面会提到的用法)
设小a初始时的黄金数量为，小b初始时的黄金数量为
小a从出发走向，小b从出发走向，两人的速度均为
假设某一时刻(必须为整数)小a的位置为，小b的位置为，若且，那么小a的黄金数量会变为，小b的黄金数量会变为
当小a到达时游戏结束
小a想知道在游戏结束时的值
答案对取模

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
//欧拉函数就是求所有小于n的与n互质的数的个数和
//n * ola(n)/2就等于所有小于n的与n互质的数字的和
ll ola(ll n){
    ll res = n;
    for(ll i = 2;i*i <= n; i++){
        if(n%i==0){
            res=res-res/i;
            do{
                n/=i;
            }while(n%i==0);
        }
    }
    if(n>1)
        res = res - res/n;
    return res;
}
//求逆原函数 b = mod-2;
ll pow_mod(ll a,ll b){
    ll  res = 1;
    while(b){
        if(b&1)
            res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    ll n,k,a,b;
    scanf("%lld %lld %lld %lld",&n,&k,&a,&b);
    ll sum = n*ola(n)/2;
    a = (a*pow_mod(k,sum))%mod;
    b = (b*pow_mod(k,sum))%mod;
    printf("%lld",(a+b)%mod);
    return 0;
}