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: competition

Starter code:

Solutions:
def __starting_point():
	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)
__starting_point()

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 = (1-Pow(q, num))%MOD*Pow((1-q)%MOD, MOD-2)%MOD
    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)


M = 0x3b9aca09
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 = list(map(int, input().split()))
s = input()

m = int(1e9 + 9)
a_1 = pow(a, m - 2, m)
x = (a_1 * b) % m
xk = pow(x, k, m)
# print("xk", xk)

C = 0
for i in range(0, k):
	z = 1 if s[i] == "+" else -1
	C = (C + z * pow(x, i, m)) % m
# print("C", C)
	
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
# print("D", D)
	
ans = pow(a, n, m) * C * D
ans %= m
print(ans)


n, a, b, k = map(int, input().split())
s = input()
mod = int(1e9 + 9)
inv = lambda x: pow(x, mod-2, mod)
q = pow(b, k, mod) * inv(pow(a, k)) % 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)

n, a, b, k = map(int, input().split())
s = input()
mod = int(1e9 + 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)
    return
z = (pow(q, t, mod) - 1) * inv(q-1) % mod
print(z * per % mod)

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 = list(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()


#def giant_steps(start, target, n=2):
    #L = [target]
    #while L[-1] > start*n:
        #L = L + [L[-1]//n + 2]
    #return L[::-1]

#def rshift(x, n):
    #if n >= 0: return x >> n
    #else:      return x << (-n)

#def lshift(x, n):
    #if n >= 0: return x << n
    #else:      return x >> (-n)
    
#def size(x):
    #return str(x).count('2')

#def newdiv(p, q):
    #szp = size(p)
    #szq = size(q)
    #szr = szp - szq
    #if min(szp, szq, szr) < 2*START_PREC:
        #return p//q
    #r = (1 << (2*START_PREC)) // (q >> (szq - START_PREC))
    #last_prec = START_PREC
    #for prec in giant_steps(START_PREC, szr):
        #a = lshift(r, prec-last_prec+1)
        #b = rshift(r**2 * rshift(q, szq-prec), 2*last_prec)
        #r = a - b
        #last_prec = prec
    #return ((p >> szq) * r) >> szr


def __starting_point():

	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)



# Made By Mostafa_Khaled

__starting_point()

MOD = 10**9+9;

n,a,b,k = list(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,p=MOD):
#    return pow(a,p-2,p);
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);


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)


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)

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)





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)


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))

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)


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)


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 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()]
#period k-1
pr=sum(s[i]*f(a,n-i)*f(b,i) for i in range(k))%mod
#ratio (b/a)^k
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)

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):
    #calculate x // y mod p
    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)

    
    

    



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)