Consider a linear function f(x) = Ax + B. Let's define g^{(0)}(x) = x and g^{(}n)(x) = f(g^{(}n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g^{(}n)(x) modulo 10^9 + 7.


-----Input-----

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 10^9, 1 ≤ n ≤ 10^18) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Output-----

Print the only integer s — the value g^{(}n)(x) modulo 10^9 + 7.


-----Examples-----
Input
3 4 1 1

Output
7

Input
3 4 2 1

Output
25

Input
3 4 3 1

Output
79

Difficulty: interview

Starter code:

Solutions:
a, b, n, x = list(map(int, input().split(' ')))
fir = pow(a, n, 10**9+7)*x%(10**9+7)
sec = b*(pow(a, n, 10**9+7)-1)*(pow(a-1, 10**9+5, 10**9+7))%(10**9+7)
if (a == 1):
    sec = n * b
print((fir+sec)%(10**9+7))


A, B, n, x = map(int, input().split())

def fast_exp(A, n, m):
    if n == 0:
        return 1
    if n & 1:
        return A * fast_exp(A, n - 1, m) % m
    return fast_exp(A * A % m, n // 2, m)

def mod(a, m):
    a %= m
    if a < 0:
        a += m
    return a

m = 10**9 + 7

if A == 1:
    print(mod(x + n * B, m))
else:
    ans = B * mod(fast_exp(A, n, m) - 1, m) % m * fast_exp(A - 1, m - 2, m) % m + fast_exp(A, n, m) * x % m
    ans %= m

    print(ans)

a,b,n,x=list(map(int,input().split()))
m=10**9+7
print(((pow(a,n,m)*x+b*(pow(a,n,m)-1)*pow(a-1,m-2,m)) if a!=1 else b*n+x)%m)


a, b, n, x = map(int, input().split())
MOD = 10 ** 9 + 7
ans = pow(a, n, MOD) * x
if a > 1:
	tmp = (pow(a, n, MOD) - 1)
	if tmp < 0:
		tmp += MOD
	tmp *= pow(a - 1, MOD - 2, MOD)
	tmp *= b
else:
	tmp = n * b
print((ans + tmp) % MOD)


def main():
    mod = 1000000007
    a, b, n, x = list(map(int, input().split()))
    if a == 1:
        print((x + n * b) % mod)
    else:
        print(((pow(a, n, mod) - 1) * pow(a - 1, mod - 2, mod) * b + pow(a, n, mod) * x) % mod)


main()


A, B, n, x = [int(i) for i in input().split()]
mod = 10**9 + 7
if A != 1:
    A_n = pow(A, n, mod)
    ans = (A_n * x) % mod + ((1 - A_n) * B * pow(1 - A, mod - 2, mod)) % mod
else:
    ans = x + B * n
ans %= mod
print(ans)


def poll(a, k):
    if k == 1:
        return a
    if k % 2 == 1:
        return poll(a * a % 1000000007, k // 2) * a % 1000000007
    return poll(a * a % 1000000007, k // 2)

a, b, n, x = [int(i) for i in input().split()]
if a != 1:
    r = poll(a, n)
    rr = r - 1
    rr *= poll((a - 1), 1000000005)
    rr *= b
    r *= x
    print((r + rr) % 1000000007)
else:
    r = x + b * n
    print(r % 1000000007)

MOD = 10 ** 9 + 7


def pow(a, n):
    res = 1
    b = a
    while n != 0:
        if n % 2:
            res = (res * b) % MOD
        n //= 2
        b = (b * b) % MOD
    return res

assert pow(2, 10) == 1024
assert pow(7, 1) == 7
assert pow(7, 0) == 1


def egcd(a, b):
    assert a > 0 and b > 0

    a_orig = a
    b_orig = b

    x0, y0 = 1, 0
    x1, y1 = 0, 1

    assert a == a_orig * x0 + b_orig * y0
    assert b == a_orig * x1 + b_orig * y1

    while b != 0:
        q = a // b

        a, b = b, a - b * q
        x0, y0, x1, y1 = x1, y1, x0 - q * x1, y0 - q * y1

        assert a == a_orig * x0 + b_orig * y0
        assert b == a_orig * x1 + b_orig * y1

    return a, x0, y0

if False:
    print(egcd(3, 5))
    print(egcd(2, 4))
    print(egcd(4, 2))
    print(egcd(5, 3))

def solve(a, b, n, x):
    if a == 1:
        return (x + b * n) % MOD

    a_n = pow(a, n)
    one, inv_a_1, _ = egcd(a - 1, MOD)
    assert one == 1
    assert ((a - 1) * inv_a_1) % MOD == 1
    res = (a_n * x + b * (a_n - 1) * inv_a_1) % MOD

    return res

if False:
    assert solve(3, 4, 2, 1) == 25
    assert solve(3, 4, 1, 1) == 7
    solve(10 ** 9 - 19, 10 ** 9 - 23, 10 ** 18 - 57, 10 ** 9 - 16)
    assert solve(1, 4, 2, 10) == 18

else:
    a, b, n, x = list(map(int, input().split()))
    print(solve(a, b, n, x))


def mod_exp(x, y, p):
    res = 1
    x %= p
    while y:
        if y&1:
            res = (res * x) % p
        y >>= 1
        x = (x * x) % p
    return res


def power(a, b, m):
    x, y = 1, a
    while b:
        if b&1:
            x = (x * y) % m
        y = (y * y) % m
        b //= 2
    return x


def mod_inverse(a, m):
    return power(a, m - 2, m)


def solve(a, b, n, x):
    m = 10**9 + 7
    if a == 1:
        return (b * n * a + x) % m
    p = mod_exp(a, n, m)
    return (b * (p - 1) * mod_inverse(a - 1, m) + p * x) % m

a, b, n, x = list(map(int, input().split()))

print(solve(a, b, n, x))


def pow(a, n):
	if (n == 0):
		return 1
	if (n % 2 == 0):
		return (pow(a, n//2) ** 2) % (1000000007)
	else:
		return (a * pow(a, n//2) ** 2) % (1000000007)



M = 1000000007
a, b, n, x = map(int, input().split())
arr = [0] * 64
arr[0] = b;
for i in range(1, 64):
	arr[i] = ((pow(a, 2**(i-1)) * arr[i-1]) % M + arr[i-1]) % M;
ans = (pow(a, n) * x) % M;
pos = 0;
for i in range(63, -1, -1):
	if (2**i <= n) :
		ans += (pow(a, pos) * arr[i]) % M;
		ans %= M;
		n -= 2**i;
		pos += 2**i;
print(ans%M)

A, B, M = 0, 0, 10**9 + 7

def GP(A,n):
    if n == 0:
        return 1
    if A == 1:
        return (n * A) % M
    res = (pow(A,n,M)-1) * pow(A-1,M-2,M)
    return res % M

def f(n,x):
    res = pow(A,n,M) * x + B * GP(A,n)
    return res % M

def g(n,x):
    if n == 0:
        return x
    elif n == 1:
        return (A*x + B) % M
    return f(n,x) % M

A, B, n, x = list(map(int,input().split()))
print(g(n,x))


def pow2(c, d):
    if d == 0:
        return 1
    if d == 1:
        return c
    return (pow2(c, d // 2) ** 2 * c ** (d % 2)) % INF

INF = 10 ** 9 + 7
a, b, n, x = list(map(int, input().split()))
if a != 1:
    SGP = ((b - b * pow2(a, n)) * pow2(1 - a, INF - 2)) % INF
else:
    SGP = b * n
print((SGP + pow2(a, n) * x) % INF)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time


(A, B, n, x) = (int(i) for i in input().split())

start = time.time()

md  = 1000000007

if A!=1 :
    an  = pow(A, n, md*(A-1))
    bn  = B*(an-1)//(A-1)
    ans = (an*x+bn)%md
else:
    ans = (x+B*n)%md
print(ans)

finish = time.time()
#print(finish - start)


a,b,n,x = map(int,input().split())
md = 10**9+7
mult  = lambda u,v : 0 if v==0 else (u+mult(u,v-1))%md if v % 2 == 1 else (2*mult(u,v//2))%md
get_prog = lambda a,b,n : mult(pow(a,n,md)-1+md,pow(a-1+md,md-2,md)) if a!=1 else n 
res = mult(pow(a,n,md),x)+mult(get_prog(a,b,n),b)
res%=md
print(res)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


mod = 10 ** 9 + 7
a, b, n, x = map(int, input().split())
ans = (pow(a, n, mod) * x % mod) % mod
if a != 1:
    ans2 = ((b * (pow(a, n, mod) - 1) % mod) * modinv(a - 1, mod)) % mod
else:
    ans2 = (b*(n*a)%mod)%mod
print((ans + ans2) % mod)

def our_sum(a, n):
    if n == 1:
        return 1
    elif n % 2 == 0:
        q = our_sum(a, n // 2)
        return (q + q * pow(a, n // 2, mod)) % mod
    else:
        return (our_sum(a, n - 1) + pow(a, n - 1, mod)) % mod


a, b, n, x = map(int, input().split())
mod = 10 ** 9 + 7
#n %= mod
res = pow(a, n, mod) * x
res %= mod
if a != 1:
    res += our_sum(a, n) * b % mod
else:
    res += b * n % mod
res %= mod
print(res)

mod = 10**9 + 7

def pow(num, p):
    nonlocal mod
    if p == 1:
        return num 
    ans = pow(num, p//2) 
    if p % 2 == 0:
        return ans * ans % mod
    else:
        return ans * ans * num % mod 

A, B, n, x = tuple(map(int, input().split()))

if A != 1:
    ans = B
    ans *= ((pow(A, n) - 1) % mod * (pow(A-1, mod - 2) % mod)) % mod
    ans += pow(A, n) * x % mod
    ans %= mod
else:
    ans = x + n * B
    ans %= mod


print(round(ans))


M = 1000000007
A, B, n, x = (int(x) for x in input().split())
if A > 1:
    An = pow(A, n, M)
    print((((An * x) % M) + (B * (1-An) * pow(1-A, M-2, M)) % M) % M)
    #print(int(An * x + B * (1-An)/(1-A)) % M)
else:
    print((x + B*n) % M)


M = int(1e9 + 7)
A, B, n, x = (int(x) for x in input().split())
if A > 1:
    An = pow(A, n, M)
    print((An * x + B * (1-An) * pow(1-A, M-2, M)) % M)
else:
    print((x + B*n) % M)



(a, b, n, x) = map(int, input().split(" "))

xp = pow(a, n % 1000000006, 1000000007)

ans = (xp * x) % 1000000007

if (a == 1):

	ans = ans + n * b

else:

	tmp = (xp - 1) * pow(a - 1, 1000000005, 1000000007) * b

	tmp = tmp % 1000000007

	ans = ans + tmp

ans = ans % 1000000007

print (ans)

a, b, n, x = map(int, input().split())
MOD = 1000000007

cur = x
while n > 0:
    if n & 1:
        cur = (a * cur + b) % MOD
    a, b = a*a % MOD, (a*b + b) % MOD
    n >>= 1
print(cur)

a, b, n, x = map(int, input().split())
MOD = 1000000007

cur = x
while n > 0:
    if n & 1:
        cur = (a * cur + b) % MOD
    a, b = a*a % MOD, (a*b + b) % MOD
    n >>= 1
print(cur)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


mod = 10 ** 9 + 7
a, b, n, x = map(int, input().split())
ans = (pow(a, n, mod) * x % mod) % mod
if a != 1:
    ans2 = ((b * (pow(a, n, mod) - 1) % mod) * modinv(a - 1, mod)) % mod
else:
    ans2 = (b*(n*a)%mod)%mod
print((ans + ans2) % mod)

q = input().split()
a = int(q[0])
b = int(q[1])
n = int(q[2])
x = int(q[3])
q = pow(a,n-1,1000000007)
x = q*a*x
if a == 1:
    q = n
else:
    q = (q-1)*pow(a-1,1000000005,1000000007)*a + 1
q = q*b+x
print(q%1000000007)

#!/usr/bin/env python3


def g(a, b, n, x, mod=10 ** 9 + 7):
    if a == 1:
        return (x + b * n) % mod
    z = pow(a, n, mod)
    inv = pow(a - 1 + mod, mod - 2, mod)
    return (z * x + b * (z - 1 + mod) * inv) % mod

print(g(*[int(x) for x in input().split()]))