963_A. Alternating Sum_8881
You are given two integers a and b. Moreover, you are given a sequence s_0, s_1, ..., 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 ≤ i ≤ n it's satisfied that s_{i} = s_{i - k}.

Find out the non-negative remainder of division of ∑ _{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 ≤ n ≤ 10^{9}, 1 ≤ a, b ≤ 10^{9}, 1 ≤ k ≤ 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:

(∑ _{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:

(∑ _{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 ≡ 999999228 \pmod{10^{9} + 9}.
from sys import stdin, stdout
from collections import Counter, defaultdict
from itertools import permutations, combinations
raw_input = stdin.readline
pr = stdout.write


def in_arr():
    return map(int,raw_input().split())


def pr_num(n):
    stdout.write(str(n)+'\n')


def pr_arr(arr):
    for i in arr:
        stdout.write(str(i)+' ')
    stdout.write('\n')

def inverse(a,m):
    return pow(a,m-2,m)

def array():
    l=raw_input().strip()
    arr=[]
    for i in l:
        if i=='+':
            arr.append(1)
        else:
            arr.append(-1)
    return arr

range = xrange # not for python 3.0+
mod=10**9+9
n,a,b,k=in_arr()
l=array()
ans=0
cm=(b*inverse(a,mod))%mod
val=pow(cm,k,mod)
x=(n+1)/k
if val>1:
    mul=((pow(val,x,mod)-1)*inverse(val-1,mod))%mod
else:
    mul=x
temp=pow(a,n,mod)
for i in range(k):
    ans=(ans+(l[i]*temp*mul))%mod
    temp=(temp*cm)%mod
pr_num(ans)

