Codeforces 678 D. Iterated Linear Function

// Accepted

// Formula: ( (A^n) - 1 / A - 1) * B + ( (A ^ n) * x)
// You have to do Modular Multiplicative Inverse due to (A - 1) ^ -1

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define mod 1000000007

LL bigmod(LL a , LL b, LL c)
{
    if(b==0) return 1;

    if(b % 2 == 0)
    {
        LL r = bigmod(a, b/2 , c);

        return ((r%c) * (r%c)) % c;
    }

    else
    {
        return (((a%c) * bigmod(a, b-1 , c) % c)) % c;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);

    LL a , b , n , x;

    while(cin >> a >> b >> n >> x)
    {
        LL tmp, t1, t2, ans;

        if(a == 1)
        {
            LL ans = (n%mod * b%mod + x) % mod;

            cout << ans << "\n";
            continue;
        }

        tmp = bigmod(a , n, mod);

        ans = ((tmp * x%mod) + b%mod * (tmp-1)%mod * bigmod(a-1, mod-2, mod)%mod)%mod;

        //t1 = ( b %mod * (tmp-1)%mod * bigmod(a-1, mod-2, mod)%mod)%mod;
        //t2 = (tmp * x%mod)%mod;

        //ans = (t1+t2);



        //ans%=mod;


        cout << ans << "\n";
    }

    return 0;
}