#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long LL;

const LL MOD = 1e9+;

LL POW(LL a,LL b)

{

    LL ans=;

    while(b)

    {

        if(b%) ans=ans*a%MOD;

        a=a*a%MOD;

        b/=;

    }

    return ans;

}

LL Euler(LL x)

{

    LL i,ans=x;

    for(i=;i<=sqrt(x);i++)

    {

        if(x%i==)

        {

            ans=ans/i*(i-)%MOD;

            while(x%i==) x/=i;

        }

    }

    if(x>)

    {

        ans=ans/x*(x-)%MOD;

    }

    return ans;

}

int main(void)

{

    LL n,k,A,B;

    while(~scanf("%lld%lld%lld%lld",&n,&k,&A,&B))

    {

        LL ans=n*Euler(n)/; //注意：这里不能对MOD取余

        ans=(A+B)%MOD*POW(k,ans)%MOD;

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

    }

    return ;

}