A recent lab accident resulted in the creation of an extremely dangerous virus that replicates so rapidly it's hard to predict exactly how many cells it will contain after a given period of time. However, a lab technician made the following observations about its growth per millisecond:

The probability of the number of virus cells growing by a factor of ${a}$ is $0.5$.
The probability of the number of virus cells growing by a factor of ${b}$ is $0.5$. 

Given ${a}$, ${b}$, and knowing that initially there is only a single cell of virus, calculate the expected number of virus cells after $\boldsymbol{\boldsymbol{t}}$ milliseconds. As this number can be very large, print your answer modulo $(10^9+7)$.

Input Format

A single line of three space-separated integers denoting the respective values of ${a}$ (the first growth factor), ${b}$ (the second growth factor), and ${t}}$ (the time you want to know the expected number of cells for).

Constraints

$1\leq t\leq10^{18}$  
$1\leq a,b\leq100$  
it is guaranteed that expected value is integer

Output Format

Print the expected number of virus cells after $\boldsymbol{\boldsymbol{t}}$ milliseconds modulo $(10^9+7)$.

Sample Input
2 4 1

Sample Output
3

Explanation

Initially, the virus has one cell. After a millisecond, with probability $0.5$, its size is doubled and, with probability of the other $0.5$ in the sample space, its size grows by ${4}$ times. Thus, the expected number of virus cell after ${1}$ millisecond is $0.5\cdot2\cdot1+0.5\cdot4\cdot1=3\%\ (10^9+7)=3$. Thus, we print $3$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Probability


Solutions:
MOD = 10 ** 9 + 7
(A, B, T) = map(int, input().split())
D = (A + B) // 2
R = 1
while T > 0:
	if T % 2:
		R = R * D % MOD
	D = D * D % MOD
	T //= 2
print(R)


(a, b, t) = (int(i) for i in input().split())
print(pow((a + b) // 2, t, 10 ** 9 + 7))


(a, b, t) = [int(x) for x in input().split(' ')]
factor = (a + b) // 2
print(pow(factor, t, 10 ** 9 + 7))


(a, b, t) = list(map(int, input().split(' ')))
tt = t
binary = '{0:b}'.format(t)
v = 1
vv = int(0.5 * (a + b)) % (10 ** 9 + 7)
while t > 0:
	if t % 2 == 1:
		v *= vv
		v = v % (10 ** 9 + 7)
	t = t // 2
	vv = vv ** 2
	vv = vv % (10 ** 9 + 7)
print(int(v))


(a, b, t) = map(int, input().split())
probA = 0.5 * a
probB = 0.5 * b
growth = (probA + probB) * 1
print(pow(int(growth), t, 10 ** 9 + 7))


(a, b, t) = [int(i) for i in input().split()]
av_virus = 1
residual_t = t
scaling = 2
base = (a + b) ** 1 // 2 ** 1
while residual_t > scaling:
	new_mult = base
	factor = 1
	while factor * scaling <= residual_t:
		factor *= scaling
		new_mult = new_mult ** scaling
		new_mult = new_mult % (10 ** 9 + 7)
	av_virus *= new_mult
	av_virus = av_virus % (10 ** 9 + 7)
	residual_t -= factor
av_virus *= base ** residual_t
av_virus = av_virus % (10 ** 9 + 7)
print(int(av_virus))


(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, 10 ** 9 + 7))


import sys
from decimal import *
(a, b, t) = [int(k) for k in input().strip().split()]
num = 0.5 * (a + b)
mod = 10 ** 9 + 7
p = getcontext().power(Decimal(num), Decimal(t), Decimal(mod))
print(p)


def mod_pow(b, e, m):
	r = 1
	b %= m
	while e > 0:
		if e % 2 == 1:
			r = r * b % m
		e >>= 1
		b = b * b % m
	return int(r)
inp = input().split()
print(mod_pow(int(0.5 * (int(inp[0]) + int(inp[1]))), int(inp[2]), pow(10, 9) + 7))


def modpower(x, y, m):
	out = int(1)
	x = int(x % m)
	while y > 0:
		if y % 2 == 1:
			out = int(x * out % m)
			y -= 1
		y = int(y >> 1)
		x = int(x * x % m)
	return out
(a, b, t) = list(map(int, input().strip().split(' ')))
e_ab = (a + b) // 2
print(int(modpower(e_ab, t, int(1000000000.0 + 7))))


(a, b, t) = (int(x) for x in input().split())
x = int((a + b) * 0.5)
p = 10 ** 9 + 7
print(pow(x, t, p))


def modulo(base, exp, mod):
	if mod == 1:
		return 0
	c = 1
	for e in range(1, exp + 1):
		c = c * base % mod
	return c

def modulo2(base, exp, mod):
	if mod == 1:
		return 0
	result = 1
	base = base % mod
	while exp > 0:
		if exp % 2 == 1:
			result = result * base % mod
		exp = exp >> 1
		base = base * base % mod
	return result

def modulo3(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
A = input().strip().split()
(a, b, t) = [int(A[0]), int(A[1]), int(A[2])]
a2 = a / 2
b2 = b / 2

def binconvert(n):
	barray = []
	if n == 0:
		return 0
	while n > 0:
		barray.append(n % 2)
		n = n >> 1
		barray.reverse()
		return barray

def modulo4(y, x, n):
	x = binconvert(x)
	s = [1]
	r = x[:]
	for k in range(0, len(x)):
		if x[k] == 1:
			r[k] = s[k] * y % n
		else:
			r[k] = s[k]
			s.append(r[k] ** 2 % n)
			return r[-1]

def modulo5(y, x, n):
	a = x
	b = 1
	c = y
	while a != 0:
		if a % 2 == 0:
			a = a / 2
			c = c ** 2 % n
		else:
			a = a - 1
			b = b * c % n
	return b
c = modulo2(int(a2 + b2), t, 1000000007)
print(int(c))


import sys

def findLargestPowerOf2(x):
	tempValue = 1
	numberOfTwos = 0
	while tempValue * 2 <= x:
		tempValue *= 2
		numberOfTwos += 1
	return numberOfTwos
(a, b, t) = input().strip().split(' ')
(a, b, t) = [int(a), int(b), int(t)]
modValue = 1000000007
growthRate = (a + b) // 2
totalGrowth = 1
while t > 0:
	if t >= 4:
		powerOf2 = findLargestPowerOf2(t)
		t -= 2 ** powerOf2
		currentGrowth = growthRate
		for x in range(powerOf2):
			currentGrowth = currentGrowth ** 2 % modValue
		totalGrowth *= currentGrowth % modValue
	if t < 4:
		if totalGrowth > 1:
			totalGrowth *= growthRate ** t % modValue
		else:
			totalGrowth = growthRate ** t % modValue
		t -= t
print(totalGrowth % modValue)


mod = 10 ** 9 + 7

def power(n, p):
	n = n % mod
	if p == 0:
		return 1
	elif p == 1:
		return n
	elif p % 2 == 0:
		tmp = power(n, p // 2) % mod
		return tmp * tmp % mod
	else:
		tmp = power(n, p // 2) % mod
		return tmp * tmp * n % mod

def num_copies_after_t(a, b, t):
	return power((a + b) // 2, t) % mod
(a, b, t) = map(int, input().split(' '))
print(num_copies_after_t(a, b, t))


inText = input()
(a, b, t) = map(int, inText.split(' '))
f = 10 ** 9 + 7
ans = pow(int(0.5 * a + 0.5 * b), t, f)
print(ans)


info = input().split()
a = int(info[0])
b = int(info[1])
t = int(info[2])
m = 10 ** 9 + 7
exp_r = (a + b) / 2
t_seq = str(bin(t))[2:][::-1]
r0 = int(exp_r % m)
res = 1
for ch in t_seq:
	if ch == '1':
		res = int(res * r0 % m)
	r0 = int(r0 * r0 % m)
print(int(res))


(a, b, t) = map(int, input().strip().split())
print(int(pow(int(0.5 * (a + b)), t, 10 ** 9 + 7)))


import sys

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
N = input().strip().split(' ')
X = int((int(N[0]) + int(N[1])) / 2)
P = 10 ** 9 + 7
Y = int(N[2])
print(power(X, Y, P))


line = input().split(' ')
a = int(line[0])
b = int(line[1])
t = int(line[2])
temp = 0.5 * (a + b)
temp = pow(int(temp), t, 1000000007)
print(temp)


(a, b, t) = [int(i) for i in input().strip().split(' ')]

def modular_power(base, exp, mod):
	res = 1
	base = base % mod
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % mod
			exp -= 1
		base = base * base % mod
		exp = exp // 2
	return res
mod = pow(10, 9) + 7
base = int(0.5 * (a + b))
res = pow(base, t, int(mod))
print(int(res))


t = input().split()
a = int(t[0])
b = int(t[1])
c = int(t[2])
r = 10 ** 9 + 7
x = (a + b) / 2
f = pow(int(x), c, r)
print(int(f))


t = input().split()
a = int(t[0])
b = int(t[1])
c = int(t[2])
r = 10 ** 9 + 7
x = (a + b) / 2
f = pow(int(x), c, r)
print(int(f))


MOD = 10 ** 9 + 7

def power(x, y):
	if y == 0:
		return 1
	tmp = power(x, y // 2) % MOD
	if y % 2 == 0:
		return tmp * tmp
	else:
		return x % MOD * tmp * tmp
s = input().split()
(a, b, t) = (int(s[0]), int(s[1]), int(s[2]))
p = power((a + b) // 2, t)
print(p % MOD)


import sys

def power(x, y, p):
	res = int(1)
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
inpSplit = input().split()
a = int(inpSplit[0]) / 2
b = int(inpSplit[1]) / 2
t = int(inpSplit[2])
mod = int(1000000000.0 + 7)
result2 = power(int(a + b), t, mod)
print(result2)


def readints():
	return list(map(int, input().strip().split()))
(a, b, t) = readints()
growth = (a + b) // 2
print(pow(growth, t, 1000000007))


import math
a = input().split()
b = (float(a[0]) + float(a[1])) / 2
print(pow(int(b), int(a[2]), 10 ** 9 + 7))


def main(x, y):
	res = 1
	x %= 1000000007
	while y > 0:
		if y & 1:
			res = res * x % 1000000007
		y >>= 1
		x = x * x % 1000000007
	return res
l = input().split()
t = int((int(l[0]) + int(l[1])) / 2)
print(main(t, int(l[2])))


(a, b, t) = [int(x) for x in input().split(' ')]
mod = 1000000007
factor = int((a + b) / 2)
population = pow(factor, t, mod)
print(population)


inputlist = [int(height_temp) for height_temp in input().strip().split(' ')]
factor = int(0.5 * inputlist[0] + 0.5 * inputlist[1])
print(int(pow(factor, inputlist[2], 1000000007)))


from sys import stdin
(a, b, t) = [int(n.strip()) for n in stdin.read().split()]
print(int(pow(int(0.5 * (a + b)), t, 10 ** 9 + 7)))


(a, b, t) = map(int, input().split())
virus = 1
power = (a + b) // 2
answer = int(pow(power, t, 10 ** 9 + 7))
print(answer)


(a, b, t) = map(int, input().split())
power = (a + b) // 2
answer = int(pow(power, t, 10 ** 9 + 7))
print(answer)


def modpow(base, exp, mod):
	if mod == 1:
		return 0
	res = 1
	base = base % mod
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % mod
		exp = exp >> 1
		base = base * base % mod
	return res
s = input()
(a, b, t) = map(int, s.split())
mod = 1000000007
result = modpow(int((a + b) / 2), t, mod)
print(int(result))


(a, b, t) = map(int, input().split())
x = int((a + b) / 2)
z = 10 ** 9 + 7
print(pow(x, t, z))


import sys
(a, b, t) = input().strip().split(' ')
(a, b, t) = [int(a), int(b), int(t)]
print(int(pow(int(0.5 * (a + b)), t, 10 ** 9 + 7)))


(a, b, t) = list(map(int, input().split()))
print(pow(int(0.5 * (a + b)), t, 1000000007))


import sys
(a, b, t) = [int(x) for x in sys.stdin.read().strip().split(' ')]
v = pow(int((a + b) * 0.5), t, pow(10, 9) + 7)
print(v)


import sys
line = sys.stdin.readline().strip('\n').split()
a = int(line[0])
b = int(line[1])
t = int(line[2])
num = pow(int(0.5 * (a + b)), int(t), pow(10, 9) + 7)
print(num)


input_vals = list(map(lambda x: int(x), input().split()))
a = input_vals[0]
b = input_vals[1]
t = input_vals[2]
expected_num = round(pow(int(0.5 * a + 0.5 * b), t, pow(10, 9) + 7))
print('{0:.0f}'.format(expected_num))


(a, b, t) = map(int, input().split(' '))
mod = 1000000007
print(pow(int((a + b) / 2), t, mod))


(a, b, t) = [int(x) for x in input().split()]
q1 = int(0.5 * (a + b))
print(pow(q1, t, 1000000007))


(a, b, t) = [int(i) for i in input().split()]
avg = int((a + b) / 2)
m = 10 ** 9 + 7
table = [avg]
for i in range(64):
	table.append(table[i] ** 2 % m)
tb = bin(t)[2:][::-1]
out = 1
for i in range(len(tb)):
	if tb[i] == '1':
		out = out * table[i] % m
print(out)


(a, b, t) = input().split()
(a, b, t) = (int(a), int(b), int(t))
value = pow(int(0.5 * (a + b)), t, 1000000007)
print(value)


import sys
(a, b, t) = [int(x) for x in input().split()]
if t == 0:
	print(1)
elif t == 1:
	print(int((a + b) / 2))
else:
	print(int(pow((a + b) // 2, t, 10 ** 9 + 7)))


(a, b, t) = map(int, input().strip().split())
k = 0.5 * (a + b)
x = pow(int(k), t, 1000000007)
print(int(round(x, 0)))


(a, b, t) = list(map(int, input().split()))
modulo = 10 ** 9 + 7
x = (a + b) // 2
print(pow(x, t, modulo))


import sys
for line in sys.stdin:
	(a, b, t) = line.split(' ')
(a, b, t) = (int(a), int(b), int(t))
fudge = 1 if (a + b) % 2 != 0 else 0
count = pow((a + b) // 2 + fudge, t, 10 ** 9 + 7)
print(count)


(a, b, t) = [int(n) for n in input().strip().split(' ')]
n = 10 ** 9 + 7
r = pow((a + b) // 2, t, n)
print(r)


def mod_pow(x, t, mod):
	if t == 1:
		return x
	elif t % 2 == 1:
		y = mod_pow(x, t // 2, mod)
		return y * y * mod_pow(x, 1, mod) % mod
	else:
		y = mod_pow(x, t // 2, mod)
		return y * y % mod
(a, b, t) = input().strip().split()
(a, b, t) = (int(a), int(b), int(t))
expected_value = mod_pow(int(0.5 * (a + b)), t, 10 ** 9 + 7)
print(int(expected_value))


import sys
import math
inputs = [int(tmp) for tmp in input().strip().split(' ')]
a = inputs[0]
b = inputs[1]
t = inputs[2]
mod = 1000000007

def mod_pow(x, y, mod):
	ans = 1
	while y:
		if y & 1:
			ans = ans * x % mod
		y >>= 1
		x = x * x % mod
	return ans
print(mod_pow(int((a + b) / 2), t, mod))


(a, b, t) = map(int, input().split())
result = 0.5 * (a + b)
something = 10 ** 9 + 7
print(int(pow(int(result), int(t), something)))


(a, b, t) = [int(i) for i in input().split()]
print(int(pow(int(0.5 * (a + b)), t, 1000000007)))


arr = [int(x) for x in input().strip().split(' ')]
a = arr[0]
b = arr[1]
t = arr[2]
x = pow(int(0.5 * a + 0.5 * b), t, 1000000007)
print(x)


(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, 10 ** 9 + 7))


(a, b, time) = (int(x) for x in input().strip().split())
c = int((a + b) * 0.5)
rem = 10 ** 9 + 7
print(pow(c, time, rem))


(a, b, c) = input().split()
(a, b, c) = (int(a), int(b), int(c))
print(pow((a + b) // 2, c, 1000000007))


import math, sys

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

def func(a, b, t):
	mod = 1000000007
	k = (a + b) / 2
	tot = pow(k, t, mod)
	return tot
for line in sys.stdin:
	(a, b, t) = [int(i) for i in line.strip().split()]
print(pow(int((a + b) / 2), t, 1000000007))


import sys
n = sys.stdin.read().strip().split()
a = int(n[0])
b = int(n[1])
t = int(n[2])
print(pow((a + b) // 2, t, 1000000007))


(a, b, t) = [int(temp) for temp in input().strip().split(' ')]
res = pow(int((a + b) / 2), t, 10 ** 9 + 7)
print(int(res))


(a, b, t) = tuple(map(int, input().split()))
q = int(0.5 * (a + b))
M = pow(10, 9) + 7
s = pow(q, t, M)
print(s)


(a, b, t) = map(int, input().split())
d = (a + b) // 2
r = 1
MOD = 10 ** 9 + 7
while t > 0:
	if t % 2:
		r = r * d % MOD
	d = d * d % MOD
	t //= 2
print(r)


(a, b, t) = [int(x) for x in input().split()]
print(pow((a + b) // 2, t, 1000000007))


import sys

def modpow(base, exponent, modulus):
	if modulus == 1:
		return 0
	c = 1
	for e_prime in range(1, exponent + 1):
		c = c * base % modulus
	return c

def modpow2(base, exponent, modulus):
	if modulus == 1:
		return 0
	result = 1
	base = base % modulus
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent = exponent >> 1
		base = base * base % modulus
	return result
(a, b, t) = map(int, sys.stdin.readline().split())
print(modpow2((a + b) // 2, t, 10 ** 9 + 7))


import sys

def power_mod(x, n, modulus):
	return pow(x, n, modulus)
(a, b, t) = list(map(int, sys.stdin.readline().strip().split()))
mean = (a + b) // 2
print(pow(mean, t, 10 ** 9 + 7))


(a, b, t) = map(int, input().split())
mod = 1000000007
print(pow((a + b) // 2, t, mod))


(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, 1000000007))


def exponentiate_mod_p(x, n, p):
	if n == 1:
		return x
	elif n % 2 == 1:
		return x * exponentiate_mod_p(x, n - 1, p) % p
	else:
		return exponentiate_mod_p(x, n // 2, p) ** 2 % p
(a, b, t) = [int(i) for i in input().split(' ')]
p = 10 ** 9 + 7
c = (a + b) // 2
n = t // (p - 1)
phi = t - n * (p - 1)
cell_count = exponentiate_mod_p(c, phi, p)
print(cell_count)


(a, b, t) = (int(i) for i in input().split())
print(pow((a + b) // 2, t, 10 ** 9 + 7))


import math
m = 1000000007
(a, b, t) = input().split()
a = int(a)
b = int(b)
t = int(t)
k = int((a + b) / 2)
print(pow(k, t, m))


modulo = 10 ** 9 + 7
(a, b, t) = [int(tmp) for tmp in input().split()]
x = pow((a + b) // 2, t, modulo)
print(x)


import sys
[a, b, t] = list(map(int, input().strip().split(' ')))
tArr = [0] * 60
index = 0
tPart = t
while tPart != 0:
	if tPart % 2 == 1:
		tArr[index] = 1
	index += 1
	tPart //= 2
fact = int((a + b) / 2)
ans = 1
tPower = fact
for i in range(60):
	if tArr[i] == 1:
		ans = ans * tPower
		ans = ans % (10 ** 9 + 7)
	tPower = tPower ** 2 % (10 ** 9 + 7)
print(int(ans))


(a, b, t) = [int(i) for i in input().strip().split(' ')]
mod = 10 ** 9 + 7

def exp(a, e):
	prod = 1
	a_pow = a
	while e > 0:
		if e % 2 == 1:
			prod *= a_pow
			if prod >= mod:
				prod %= mod
		a_pow *= a
		if a_pow >= mod:
			a_pow %= mod
		e >>= 1
	return prod

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
if a < b:
	(a, b) = [b, a]
if (a + b) % 2 == 0:
	print(pow((a + b) // 2, t, mod))
else:
	print(pow(a + b, t, mod) * modinv(pow(2, t, mod), mod) % mod)


import math

def powerModule(x, y, m):
	t = y
	Lp2 = []
	while t > 0:
		exp = int(math.log(t) / math.log(2))
		p2 = 2 ** exp
		t = t - p2
		Lp2.append(p2)
	Lp2.reverse()
	res = 1
	exp = 0
	i = 0
	while i < len(Lp2):
		if 2 ** exp == Lp2[i]:
			res = res * x % m
			i += 1
		x = x * x % m
		exp += 1
	return res
[a, b, t] = [int(x) for x in input().split(' ')]
res = powerModule(int(0.5 * a + 0.5 * b), t, 10 ** 9 + 7)
print(int(res))


(a, b, t) = input().split()
(a, b, t) = (int(a), int(b), int(t))
c = int((a + b) / 2)
answer = pow(c, t, 10 ** 9 + 7)
print(int(answer))


def f(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
(a, b, t) = [int(x) for x in input().split()]
new_rate = (a + b) // 2
print(int(pow(new_rate, t, 10 ** 9 + 7)))


(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, 1000000007))


t = input().split()
a = int(t[0])
b = int(t[1])
time = int(t[2])
k = 10 ** 9 + 7
rate = int((a + b) / 2)
print(pow(rate, time, k))


(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, 10 ** 9 + 7))


MOD = 10 ** 9 + 7
(A, B, T) = map(int, input().split())
D = (A + B) // 2
R = 1
while T > 0:
	if T % 2:
		R = R * D % MOD
	D = D * D % MOD
	T //= 2
print(R)


(a, b, t) = input().strip().split()
(a, b, t) = (int(a), int(b), int(t))
print(pow(int((a + b) / 2), t, 1000000007))


import sys
for line in sys.stdin:
	(a, b, t) = map(int, line.split(' '))
	a /= 2
	b /= 2
	ans = pow(int(a + b), t, 10 ** 9 + 7)
	print('{:.0f}'.format(ans))


P = 10 ** 9 + 7
(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, P))


def f(a, b, n):
	mod = 10 ** 9 + 7
	x = (a + b) // 2
	while n % 2 != 1:
		x *= x
		x = x % mod
		n //= 2
	p = x
	n //= 2
	while n > 0:
		x *= x
		x = x % mod
		if n % 2 == 1:
			p *= x
			p = p % mod
		n //= 2
	return int(p)
(a, b, n) = (int(i) for i in input().split())
print(f(a, b, n))


import sys
(a, b, t) = [int(x) for x in sys.stdin.readline().split()]
print(pow((a + b) // 2, t, 1000000007))


b = input().split()
a = []
for i in b:
	a.append(int(i))
d = int((a[0] + a[1]) / 2)
e = int(a[2])
print(pow(d, e, 1000000007))


(a, b, t) = map(int, input().split())
print(pow((a + b) // 2, t, 10 ** 9 + 7))


(a, b, t) = map(int, input().split())
print(int(pow(int((a + b) / 2), t, 1000000007)))


(a, b, t) = map(int, input().split())
n = pow((a + b) // 2, t, 1000000007)
print(n)


(a, b, t) = map(int, input().split())
e = a * 0.5 + b * 0.5
e = int(e)
r = pow(e, t, 10 ** 9 + 7)
print(int(r))


(a, b, t) = [int(i) for i in input().split()]
c = pow(int((a + b) / 2), t, 1000000007)
print(int(c))


(a, b, t) = [int(x) for x in input().strip().split()]
print(pow((a + b) // 2, t, 10 ** 9 + 7))


def FastExpMod(i, n, MOD):
	res = 1
	while n != 0:
		if n % 2 == 1:
			res *= i
			res %= MOD
		i *= i
		i %= MOD
		n >>= 1
	return res
(A, B, T) = list(map(int, input().strip().split()))
C = (A + B) // 2
res = FastExpMod(C, T, 1000000007)
print(res)


import math

def get_chooses(n):
	chooses = [1]
	while len(chooses) < n:
		new_chooses = [1]
		for i in range(len(chooses) - 1):
			new_chooses.append(chooses[i] + chooses[i + 1])
		new_chooses.append(1)
		chooses = new_chooses
	return chooses
(a, b, t) = list(map(int, input().split(' ')))
expected = 0
print(pow((a + b) // 2, t, 10 ** 9 + 7))


[a, b, t] = input().split()
c = (int(a) + int(b)) // 2
print(pow(c, int(t), 1000000007))


mod = 1000000007
(a, b, t) = map(int, input().split())

def fastexpo(a, t, mod):
	if t == 0:
		return 1
	if t == 1:
		return a
	if t % 2:
		return a * fastexpo(a * a % mod, (t - 1) // 2, mod) % mod
	return fastexpo(a * a % mod, t // 2, mod)
print(int(fastexpo(int(a / 2 + b / 2), t, mod)) % mod)


import math
(a, b, t) = list(map(int, input().split(' ')))
C = 10 ** 9 + 7
D = (a + b) // 2
print(pow(D, t, C))


import sys
v = input().split(' ')
i = list(map(int, v))
print(pow(int((i[0] + i[1]) * 0.5), i[2], 10 ** 9 + 7))


def exp(a, b, t):
	result = pow((a + b) // 2, t, int(10 ** 9 + 7))
	return int(result)
(a, b, t) = [int(x) for x in input().strip().split()]
print(exp(a, b, t))


a = input()
a = a.split()
a = list(map(int, a))
result = pow(int((a[0] + a[1]) / 2), a[2], 1000000007)
print(int(result))


(a, b, t) = map(int, input().split())
k = (a + b) // 2
print(pow(k, t, 10 ** 9 + 7))