You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It's known that sequence is $k$-periodic and $k$ divides $n+1$. In other words, for each $k \leq i \leq n$ it's satisfied that $s_{i} = s_{i - k}$.

Find out the non-negative remainder of division of $\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$ by $10^{9} + 9$.

Note that the modulo is unusual!


-----Input-----

The first line contains four integers $n, a, b$ and $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$.

The second line contains a sequence of length $k$ consisting of characters '+' and '-'. 

If the $i$-th character (0-indexed) is '+', then $s_{i} = 1$, otherwise $s_{i} = -1$.

Note that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property.


-----Output-----

Output a single integer — value of given expression modulo $10^{9} + 9$.


-----Examples-----
Input
2 2 3 3
+-+

Output
7

Input
4 1 5 1
-

Output
999999228



-----Note-----

In the first example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i})$ = $2^{2} 3^{0} - 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7

In the second example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}) = -1^{4} 5^{0} - 1^{3} 5^{1} - 1^{2} 5^{2} - 1^{1} 5^{3} - 1^{0} 5^{4} = -781 \equiv 999999228 \pmod{10^{9} + 9}$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def pow_mod(x, y, p):
	number = 1
	while y:
		if y & 1:
			number = number * x % p
		y >>= 1
		x = x * x % p
	return number % p

def inv(x, p):
	if 1 < x:
		return p - inv(p % x, x) * p // x
	return 1

def v(p, a, b, k):
	i = 1
	while pow_mod(a, k, (10 ** 9 + 9) ** i) - pow_mod(b, k, (10 ** 9 + 9) ** i) == 0:
		i += 1
	return i - 1

def main():
	p = 10 ** 9 + 9
	(n, a, b, k) = map(int, input().split())
	S = list(input())
	for i in range(k):
		if S[i] == '+':
			S[i] = 1
		else:
			S[i] = -1
	s = 0
	if a != b:
		vp = p ** v(p, a, b, k)
		sum_mod = (pow_mod(a, n + 1, p * vp) - pow_mod(b, n + 1, p * vp)) // vp * inv((pow_mod(a, k, p * vp) - pow_mod(b, k, p * vp)) // vp % p, p)
		pa = pow_mod(a, k - 1, p)
		pb = 1
		inv_a = inv(a, p)
		for i in range(k):
			s += S[i] * pa * pb * sum_mod % p
			pa = pa * inv_a % p
			pb = pb * b % p
	else:
		for i in range(k):
			s += S[i] * (n + 1) // k
		s *= pow_mod(a, n, p)
	s %= p
	print(s)
main()


(n, a, b, k) = map(int, input().split())
s = input()
m = int(1000000000.0 + 9)
a_1 = pow(a, m - 2, m)
x = a_1 * b % m
xk = pow(x, k, m)
C = 0
for i in range(0, k):
	z = 1 if s[i] == '+' else -1
	C = (C + z * pow(x, i, m)) % m
kk = (n + 1) // k
if xk > 1:
	v1 = (pow(xk, kk, m) - 1) % m
	v2 = pow((xk - 1) % m, m - 2, m)
	D = v1 * v2 % m
else:
	D = kk
ans = pow(a, n, m) * C * D
ans %= m
print(ans)


mod = 1000000009

def inv(x):
	return pow(x, mod - 2, mod)
(n, a, b, k) = map(int, input().split())
s = input()
q = pow(b, k, mod) * inv(pow(a, k, mod))
t = 0
for i in range(k):
	sgn = 1 if s[i] == '+' else -1
	t += sgn * pow(a, n - i, mod) * pow(b, i, mod)
	t %= mod
	t += mod
	t %= mod
print((t * (1 - pow(q, (n + 1) // k, mod)) * inv(1 - q) % mod + mod) % mod if q != 1 else t * (n + 1) // k % mod)


M = 1000000009
inv = lambda x: pow(x, M - 2, M)
(n, a, b, k) = list(map(int, input().split()))
s = input()
c = inv(a) * b % M
q = pow(c, k, M)
m = (n + 1) // k
p = (pow(q, m, M) - 1) * inv(q - 1) % M if q - 1 else m
x = pow(a, n, M)
r = 0
for i in range(k):
	r = (r + [-1, 1][s[i] == '+'] * x * p) % M
	x = x * c % M
print(r)


(n, a, b, k) = map(int, input().split())
s = input()
mod = int(1000000000.0 + 9)
inv = lambda x: pow(x, mod - 2, mod)
q = pow(b, k, mod) * inv(pow(a, k, mod)) % mod
per = 0
d = pow(a, n, mod)
qq = b * inv(a) % mod
for i in range(k):
	if s[i] == '+':
		per += d
	else:
		per -= d
	per %= mod
	d = d * qq % mod
t = (n + 1) // k
if q == 1:
	print(t * per % mod)
	exit(0)
z = (pow(q, t, mod) - 1) * inv(q - 1) % mod
print(z * per % mod)


MOD = 10 ** 9 + 9
(n, a, b, k) = map(int, input().split())
s = input()

def pow(a, n, m=MOD):
	ret = 1
	a %= MOD
	while n:
		if n & 1:
			ret = ret * a % m
		a = a * a % m
		n >>= 1
	return ret

def inv(a, m=MOD):
	if a > 1:
		return (m - m // a * inv(m % a, m)) % m
	return 1
(ia, d) = (inv(a), (n + 1) // k)
(ans, ci0, q) = (0, pow(a, n), pow(ia * b, k))
Q = d
if q != 1:
	Q = (pow(q, d) - 1) * inv(q - 1) % MOD
for i in range(k):
	sign = 1
	if s[i] == '-':
		sign = -1
	ans += sign * ci0 * Q % MOD
	ans %= MOD
	ci0 = ci0 * ia * b % MOD
print(ans)


a = [int(x) for x in input().split()]
N = a[0]
A = a[1]
B = a[2]
K = a[3]
s = input()
mod = 1000000009
Q = pow(B * pow(A, mod - 2, mod) % mod, K, mod)
if Q != 1:
	D = (pow(Q, (N + 1) // K, mod) - 1) * pow(Q - 1, mod - 2, mod) % mod
else:
	D = (N + 1) // K
ans = 0
C = pow(A, N, mod)
A = pow(A, mod - 2, mod)
for i in range(K):
	if s[i] == '+':
		ans = (ans + C * D) % mod
	else:
		ans = (ans - C * D) % mod
	C = C * B * A % mod
print((ans % mod + mod) % mod)


raw = input().split()
vals = [x for x in input()]
(n, a, b, k) = [int(x) for x in raw]
summ = 0
mod = 1000000009

def inv(x):
	return fast_power(x, mod - 2)

def fast_power(a, n):
	ret = 1
	a = a % mod
	while n:
		if n & 1:
			ret = ret * a % mod
		a = a * a % mod
		n >>= 1
	return ret
c = inv(a) * b % mod
cf = fast_power(c, k)
m = (n + 1) // k
if cf - 1:
	p = (fast_power(cf, m) - 1) * inv(cf - 1) % mod
else:
	p = m
x = fast_power(a, n)
for i in range(k):
	summ = (summ + [-1, 1][vals[i] == '+'] * x * p) % mod
	x = x * c % mod
print(summ)


def alternatingSum(n, a, b, k, s):
	mod = 1000000009
	inv = lambda x: pow(x, mod - 2, mod)
	q = pow(b, k, mod) * inv(pow(a, k, mod)) % mod
	per = 0
	d = pow(a, n, mod)
	qq = b * inv(a) % mod
	for i in range(k):
		if s[i] == '+':
			per += d
		else:
			per -= d
		per %= mod
		d = d * qq % mod
	t = (n + 1) // k
	if q == 1:
		print(t * per % mod)
		return
	z = (pow(q, t, mod) - 1) * inv(q - 1) % mod
	print(z * per % mod)
paramsRaw = input()
paramsStr = paramsRaw.split()
paramsInt = list(map(int, paramsStr))
sequenceRaw = input()
alternatingSum(paramsInt[0], paramsInt[1], paramsInt[2], paramsInt[3], sequenceRaw)


import queue

def readTuple():
	return input().split()

def readInts():
	return tuple(map(int, readTuple()))

def egcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise AtributeError(a, m)
	else:
		return x % m

def solve():
	MOD = 10 ** 9 + 9
	(n, a, b, k) = readInts()
	vals = input().strip()
	base = 0
	BB = 1
	for (i, v) in enumerate(vals):
		if v == '+':
			base += pow(a, n - i, MOD) * BB
		else:
			base -= pow(a, n - i, MOD) * BB
		base %= MOD
		BB = BB * b % MOD
	l = (n + 1) // k
	xx = pow(modinv(a, MOD) * b, k, MOD)
	if xx != 1:
		mul = (1 - pow(xx, l, MOD)) * modinv(1 - xx, MOD) % MOD
	else:
		mul = l
	print(base * mul % MOD)
solve()


(n, a, b, k) = list(map(int, input().split()))
s = str(input())
MOD = 10 ** 9 + 9

def fun(a, b, i):
	return pow(a, n - i, MOD) * pow(b, i, MOD) % MOD

def div(x, y):
	return x * pow(y, MOD - 2, MOD) % MOD
r = pow(div(b, a), k, MOD)
SUM = 0
for i in range(k):
	if s[i] == '-':
		SUM += -1 * fun(a, b, i)
	else:
		SUM += +1 * fun(a, b, i)
n += 1
t = n // k
ans = pow(r, t, MOD) - 1
x = r - 1
if x:
	ans = div(ans, x) * SUM % MOD
else:
	ans = t * SUM % MOD
ans += MOD
ans %= MOD
print(ans)


MOD = 1000000009

def inv(n):
	return pow(n, MOD - 2, MOD)
(n, a, b, k) = map(int, input().split())
q = (n + 1) // k
string = input()
s = []
for char in string:
	if char == '+':
		s.append(1)
	else:
		s.append(-1)
res = 0
for i in range(k):
	res += s[i] * pow(a, n - i, MOD) * pow(b, i, MOD)
	res %= MOD
n1 = pow(b, k, MOD)
n2 = pow(a, k, MOD)
n2 = inv(n2)
T = n1 * n2 % MOD
if T != 1:
	num = (pow(b, n + 1, MOD) - pow(a, n + 1, MOD)) % MOD
	d1 = (pow(b, k, MOD) - pow(a, k, MOD)) % MOD
	d1 = inv(d1)
	d2 = pow(a, n + 1 - k, MOD)
	d2 = inv(d2)
	R = num * d1 * d2 % MOD
	res = res * R % MOD
	print(res)
else:
	res *= q
	res %= MOD
	print(res)


mod = 10 ** 9 + 9

def gcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(d0, x0, y0) = gcd(b % a, a)
	x = y0 - b // a * x0
	y = x0
	return (d0, x, y)

def pow(a, k):
	if k == 0:
		return 1
	if k == 1:
		return a
	if k % 2 == 1:
		return pow(a, k - 1) * a % mod
	return pow(a, k // 2) ** 2 % mod
(n, a, b, k) = map(int, input().split())
s = input()
pa = [1]
pb = [1]
for i in range(k):
	pa.append(pa[-1] * a % mod)
	pb.append(pb[-1] * b % mod)
ak = pa[k]
ans = pow(ak, (n + 1 - k) // k)
sk = 0
for i in range(k):
	if s[k - i - 1] == '+':
		sk += pb[k - i - 1] * pa[i] * ans % mod
	else:
		sk -= pb[k - i - 1] * pa[i] * ans % mod
while sk < 0:
	sk += mod
inva = list(gcd(ak, mod))[1]
inva = inva % mod
while inva < 0:
	inva += mod
ans = 0
bk = pb[k]
ak = inva
q = ak * bk % mod
c = (n + 1) // k
if q == 1:
	print(sk * c % mod)
	exit(0)
if q == 0:
	print(sk)
	exit(0)
qn = pow(q, c)
invq = list(gcd(q - 1, mod))[1] % mod
while invq < 0:
	invq += mod
print(sk * (qn - 1) * invq % mod)


MOD = 1000000009

def xpow(desk, step):
	ret = 1
	desk = desk % MOD
	while step:
		if step % 2:
			ret = ret * desk % MOD
		step = step // 2
		desk = desk * desk % MOD
	return ret
(n, a, b, k) = map(int, input().split())
s = input()
base = 0
for i in range(0, k):
	base = (base + [-1, 1][s[i] == '+'] * (xpow(a, n - i) * xpow(b, i))) % MOD
loop = (n + 1) // k
a = xpow(a, k)
b = xpow(b, k)
if a != b:
	print((xpow(b, loop) - xpow(a, loop)) * xpow(b * xpow(a, loop - 1) - xpow(a, loop), MOD - 2) % MOD * base % MOD)
else:
	print(base * loop % MOD)


import sys
try:
	fin = open('in')
except:
	fin = sys.stdin
input = fin.readline
mod = 10 ** 9 + 9

def f(x, y):
	ans = 1
	while y:
		if y & 1:
			ans = ans * x % mod
		x = x * x % mod
		y >>= 1
	return ans
(n, a, b, k) = map(int, input().split())
s = [1 if c == '+' else -1 for c in input()]
pr = sum((s[i] * f(a, n - i) * f(b, i) for i in range(k))) % mod
rt = f(b, k) * f(f(a, k), mod - 2) % mod
terms = (n + 1) // k
if rt == 1:
	print(terms * pr % mod)
else:
	print(pr * (f(rt, terms) - 1) * f(rt - 1, mod - 2) % mod)


import math

def binpow(a, b, m):
	a %= m
	res = int(1)
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def inv(a, m: int=1000000009):
	return binpow(a, m - 2, m)
m = int(1000000009)
(n, a, b, k) = input().split()
n = int(n)
a = int(a)
b = int(b)
k = int(k)
st = input()
res = int(1)
p = int(b * inv(a, m) % m)
itr = (n + 1) // k
mul1 = 0
for i in range(len(st)):
	if st[i] == '+':
		mul1 = (mul1 + binpow(p, i, m)) % m
	else:
		mul1 = (mul1 - binpow(p, i, m)) % m
if binpow(p, k, m) == 1:
	mul2 = itr % m
else:
	mul2 = (binpow(p, k * itr, m) - 1) * inv((binpow(p, k, m) - 1) % m) % m
res = mul1 * mul2 % m
left = n - k * itr + 1
mul1 = binpow(p, k * itr, m)
mul2 = 0
for i in range(left):
	if st[i] == '+':
		mul2 = (mul2 + binpow(p, i, m)) % m
	else:
		mul2 = (mul2 - binpow(p, i, m)) % m
res = (res + mul1 * mul2) % m
res = res * binpow(a, n, m) % m
print(res)


import sys
MOD = 10 ** 9 + 9

def inv(x):
	return pow(x, MOD - 2, MOD)

def alternateSum(n, a, b, k, s):
	res = 0
	q = pow(b, k, MOD) * inv(pow(a, k, MOD)) % MOD
	max_pow = pow(a, n, MOD)
	c = b * inv(a) % MOD
	for i in range(k):
		if s[i] == '+':
			res += max_pow
		elif s[i] == '-':
			res -= max_pow
		res %= MOD
		max_pow = max_pow * c % MOD
	t = (n + 1) // k
	if q == 1:
		return t * res % MOD
	z = (pow(q, t, MOD) - 1) * inv(q - 1) % MOD
	return z * res % MOD
(n, a, b, k, s) = sys.stdin.read().split()
result = alternateSum(int(n), int(a), int(b), int(k), s)
print(result)


(n, a, b, k) = [int(i) for i in input().split()]
st = input()
l = (n + 1) // k
s = 0
mod = 1000000009

def f_pow(a, k):
	if k == 0:
		return 1
	if k % 2 == 1:
		return f_pow(a, k - 1) * a % mod
	else:
		return f_pow(a * a % mod, k // 2) % mod

def rev(b):
	return f_pow(b, mod - 2)
q = f_pow(b, k) * rev(f_pow(a, k))
qn = f_pow(q, l)
rq = rev(q - 1)
g1 = f_pow(a, n)
ra = rev(a)
for i in range(len(st)):
	sgn = 1 - 2 * (st[i] == '-')
	res = g1 * (qn - 1) * rq
	if q % mod != 1:
		s = (s + sgn * res) % mod
	else:
		s = (s + sgn * g1 * l) % mod
	g1 = g1 * ra * b % mod
print(s)


(n, a, b, k) = map(int, input().split())
mod = 10 ** 9 + 9
s = input()

def func(string):
	if string == '+':
		return 1
	return -1

def rev(d):
	return pow(d, mod - 2, mod)
R = pow(b * rev(a), k, mod)
seq = [func(s[i]) for i in range(k)]
if n + 1 <= k:
	ans = sum((seq[i] * pow(a, n - i, mod) * pow(b, i, mod) for i in range(n + 1))) % mod
	print(ans)
	exit()
S0 = sum((seq[i] * pow(a, n - i, mod) * pow(b, i, mod) for i in range(k))) % mod
(u, v) = divmod(n + 1, k)
ans = 0
if R != 1:
	ans += S0 * (pow(R, u, mod) - 1) * rev(R - 1)
else:
	ans += u * S0
if v > 0:
	left = sum((seq[i] * pow(a, n - i, mod) * pow(b, i, mod) for i in range(v - 1))) % mod
	ans += pow(R, u, mod) * left % mod
print(ans % mod)


MOD = int(1000000000.0 + 9)
(n, a, b, k) = map(int, input().split())
s = input()

def solve():
	res = 0
	q = pow(b, k, MOD) * pow(pow(a, k, MOD), MOD - 2, MOD) % MOD
	max_pow = pow(a, n, MOD)
	c = b * pow(a, MOD - 2, MOD) % MOD
	for i in range(k):
		res += max_pow if s[i] == '+' else -max_pow
		res = (res % MOD + MOD) % MOD
		max_pow = max_pow * c % MOD
	t = (n + 1) // k
	if q == 1:
		return t * res % MOD
	z = (pow(q, t, MOD) - 1) * pow(q - 1, MOD - 2, MOD) % MOD
	return z * res % MOD
print(solve())


import sys
input = sys.stdin.readline
(n, a, b, k) = map(int, input().split())
s = input().rstrip()
mod = 10 ** 9 + 9
pa = pow(a, n, mod)
inv_a = pow(a, mod - 2, mod)
pb = 1
xk = 0
for i in range(k):
	if s[i] == '+':
		xk += pa * pb % mod
		xk %= mod
	else:
		xk -= pa * pb % mod
		xk %= mod
	pa *= inv_a
	pa %= mod
	pb *= b
	pb %= mod
y = (1 - pow(inv_a * b % mod, n + 1, mod)) % mod
zz = pow(inv_a * b % mod, k, mod)
if zz != 1:
	z = (1 - zz) % mod
	z = pow(z, mod - 2, mod)
	print(xk * y * z % mod)
else:
	z = (n + 1) // k
	print(z * xk % mod)


(n, a, b, k) = map(int, input().split())
s = input()
mod = int(1000000000.0 + 9)
ans = 0
t = int((n + 1) / k)

def modInverse(a):
	return pow(a, mod - 2, mod)
i = 0
for ind in range(len(s)):
	first = pow(a, n - i, mod) * pow(b, i, mod) % mod
	num = pow(b, k, mod) * modInverse(pow(a, k, mod)) % mod
	if b >= a:
		den = (num - 1 + mod) % mod
		num = (pow(num, t, mod) - 1 + mod) % mod
	else:
		den = (1 - num + mod) % mod
		num = (1 - pow(num, t, mod) + mod) % mod
	if num == 0:
		temp = t * first % mod
	else:
		temp = num * modInverse(den) % mod
		temp = temp * first % mod
	if s[ind] == '+':
		ans = (ans + temp) % mod
	elif s[ind] == '-':
		ans = (ans - temp + mod) % mod
	i += 1
	if i > n:
		i = 0
print(ans)


MOD = 1000000009

def Pow(base, n):
	res = 1
	while n:
		if n & 1:
			res = res * base % MOD
		base = base * base % MOD
		n >>= 1
	return res
(n, a, b, k) = list(map(int, input().split()))
ans = 0
num = (n + 1) // k
_a = Pow(a, MOD - 2)
q = Pow(b, k) * Pow(Pow(a, k), MOD - 2) % MOD
if q == 1:
	res = Pow(a, n) * num % MOD
	for i in input():
		if i == '+':
			ans = (ans + res) % MOD
		else:
			ans = (ans - res) % MOD
		res = res * b % MOD * _a % MOD
else:
	rat = (Pow(q, num) - 1) % MOD * Pow((q - 1) % MOD, MOD - 2) % MOD
	cur = Pow(a, n) * rat % MOD
	for i in input():
		if i == '+':
			ans = (ans + cur) % MOD
		else:
			ans = (ans - cur) % MOD
		cur = cur * b % MOD * _a % MOD
print(ans)


inp = input('').split('\n')
nums = inp[0].split(' ')
n = int(nums[0])
a = int(nums[1])
b = int(nums[2])
k = int(nums[3])
st = str(input('').strip())
tot = 0
mod = 10 ** 9 + 9

def inv(a):
	return pow(a, mod - 2, mod)
for i in range(0, k):
	vl = 1
	if st[i] == '-':
		vl = -1
	tot += vl * pow(a, n - i, mod) * pow(b, i, mod)
	tot %= mod
mult = pow(b, k, mod) * inv(pow(a, k, mod)) % mod
p = (n + 1) // k - 1
if mult == 1:
	print(tot * (p + 1) % mod)
else:
	num = (pow(mult, p + 1, mod) - 1) % mod
	den = (mult - 1) % mod
	num = num * inv(den) % mod
	print(num * tot % mod)


MOD = 1000000009

def AlternateSum(n, a, b, k, s):
	res = 0
	inv = lambda x: pow(x, MOD - 2, MOD)
	q = pow(b, k, MOD) * inv(pow(a, k, MOD)) % MOD
	max_pow = pow(a, n, MOD)
	c = b * inv(a) % MOD
	for i in range(k):
		if s[i] == '+':
			res += max_pow
		else:
			res -= max_pow
		res %= MOD
		max_pow = max_pow * c % MOD
	t = (n + 1) // k
	if q == 1:
		return t * res % MOD
	z = (pow(q, t, MOD) - 1) * inv(q - 1) % MOD
	return z * res % MOD
(n, a, b, k) = [int(x) for x in input().split()]
s = input()
print(AlternateSum(n, a, b, k, s))