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}.
import java.util.*;
import java.math.*;
import java.io.*;

public class CF964C implements Runnable {

	final int MOD = (int) 1e9 + 9; // weird modulo
	final double ERROR = 1e-9;
	final double oo = 1e50;
	long invA, c;
	
	public void run() {
		FastScanner scan = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt();
		int a = scan.nextInt();
		int b = scan.nextInt();
		int k = scan.nextInt();
		invA = modInv(a);
		c = (modExp(invA, k) * modExp(b, k)) % MOD;
		char[] s = scan.next().toCharArray();
		long res = 0;
		for(int i = 0 ; i < s.length ; i++) {
			if(s[i] == '+') {
				res += solve(i, k, n, a, b);
				if(res >= MOD)
					res -= MOD;
			} else {
				res -= solve(i, k, n, a, b);
				if(res < 0)
					res += MOD;
			}
		}
		out.println(res);
		out.close();
	}
	
	long solve(int i, int k, int n, long a, long b) {
		long f0 = (modExp(a, n - i) * modExp(b, i)) % MOD;
		long[][] mat1 = {{1, 1}, 
		                 {0, c}};
		long[][] mat2 = {{ 0}, 
		                 {f0}};
		mat1 = matExp(mat1, (n + 1) / k);
		mat2 = mult2x1(mat1, mat2);
		return mat2[0][0];
	}
	
	long modInv(long x) {
		return modExp(x, MOD - 2);
	}
	
	long modExp(long b, long e) {
		if(e == 0)
			return 1L;
		if((e & 1) == 0) {
			long tmp = modExp(b, e / 2);
			return (tmp * tmp) % MOD;
		} else {
			return (b * modExp(b, e - 1)) % MOD;
		}
	}
	
	long[][] identity = {{1, 0}, 
	                     {0, 1}};
	long[][] matExp(long[][] m, long exp) {
		if(exp == 0L)
			return identity;
		if((exp & 1) == 0) {
			long[][] res = matExp(m, exp/2);
			return mult2x2(res, res);
		}
		return mult2x2(m, matExp(m, exp-1));
	}

	long[][] mat2x2 = new long[2][2];
	long[][] mult2x2(long[][] a, long[][] b) {
		mat2x2[0][0] = (((a[0][0] * b[0][0]) % MOD) + ((a[1][0] * b[0][1]) % MOD));
		if(mat2x2[0][0] >= MOD) mat2x2[0][0] += MOD;
		mat2x2[0][1] = (((a[0][1] * b[0][0]) % MOD) + ((a[1][1] * b[0][1]) % MOD));
		if(mat2x2[0][1] >= MOD) mat2x2[0][1] += MOD;
		mat2x2[1][0] = (((a[0][0] * b[1][0]) % MOD) + ((a[1][0] * b[1][1]) % MOD));
		if(mat2x2[1][0] >= MOD) mat2x2[1][0] += MOD;
		mat2x2[1][1] = (((a[0][1] * b[1][0]) % MOD) + ((a[1][1] * b[1][1]) % MOD));
		if(mat2x2[1][1] >= MOD) mat2x2[1][1] += MOD;
		return mat2x2;
	}
	
	long[][] mat2x1 = new long[2][1];
	long[][] mult2x1(long[][] a, long[][] b) {
		mat2x1[0][0] = (((b[0][0] * a[0][0]) % MOD) + ((b[1][0] * a[0][1]) % MOD));
		if(mat2x1[0][0] >= MOD) mat2x1[0][0] += MOD;
		mat2x1[1][0] = (((b[0][0] * a[1][0]) % MOD) + ((b[1][0] * a[1][1]) % MOD));
		if(mat2x1[1][0] >= MOD) mat2x1[1][0] += MOD;
		return mat2x1;
	}

	class FastScanner {
		BufferedReader br; StringTokenizer st;
		public FastScanner() {
			try {
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}
		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}

	public static void main(String[] args) {
		new Thread(null, new CF964C(), "_cf", 1 << 28).start();
	}
}
/*

8 2 3 3
-+-
8 2 3 9
-+--+--+-

3 2 3 4
+-+-
3 2 3 2
+-

*/