题意：a， b两个人在长度为n的一维数轴上（从1开始）。a在1，b在n。每个人以1m/s的速度相向而行，则每一时刻存在坐标x，y，当cgd(n, x)==1,gcd(n, y)==1时，t1=k^x, t2=k^y. 。然后每个t对应相乘，再相加。
思路：a,b其实的x,y坐标都是相同的。首先，要知道。设x<n,gcd(n,x)==1,则gcd(n, n-x)==1.那么则将题转化为n以内的与n互素的数之和。
那么引出欧拉函数的一条拓展定义：在n以内所有与n互素的所有数之和为n*Φ(n)/2
#include<iostream>
using namespace std;
#define ll long long
const int mod = 1e9 + ;
ll euler(ll x){
ll ret = x;
for (ll i = ; i*i <= x; ++i){
if (x%i == ){
ret = ret / i*(i - );
while (x%i == )x /= i;
}
}
if (x > )ret = ret / x*(x - );
return ret;
}
ll Pow(ll x, ll n){
ll ans = ;
for (; n; x = x*x%mod, n >>= )
if (n & )ans = ans*x%mod;
return ans;
}
int main(){
std::ios::sync_with_stdio(false);
ll n, k, a, b;
cin >> n >> k >> a >> b;
ll c = (a + b) % mod; cout << c*Pow(k, n*euler(n)/%mod) % mod << endl;
}