963_A. Alternating Sum_8884
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.io.*;
/*
	1
7
8 6 12 10 12 8 10


4
4
1 2 1 1 
2 2 2 1
10 6 11 10
 */
public class Crypto {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		PrintWriter out = new PrintWriter(System.out);
		Scanner sc = new Scanner(System.in);
		final int MOD = 1000000009;
		long n = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt(), k = sc.nextInt();
		sc.nextLine();
		char ch[] = sc.nextLine().toCharArray();
		long A = 0, N = (n+1)/k, r = powerMod((b * powerMod(a, MOD-2, MOD))%MOD, k, MOD);
		for(int i = 0; i<k; i++) {
			long temp = 1;
			if(ch[i] == '-') temp = -1;
			A = ( A + (temp * powerMod(a,n-i,MOD) * powerMod(b, i, MOD))%MOD + MOD)%MOD;
			//System.out.println(A);
			//A = (A+MOD)%MOD;
		}
		long fa = 0;
		if(r==1) {
			fa = (N*A)%MOD;
		}
		else {
			long a1 = (powerMod(r, N, MOD) -1 + MOD)%MOD;
			long a2 = powerMod((r-1+MOD)%MOD, MOD-2, MOD);
			fa = (A * ((a1 * a2)%MOD))%MOD;
		}
		//System.out.println(A+" "+r+" "+N);
		System.out.println((fa+MOD)%MOD);
		out.close();
	}
	static long powerMod(long a, long b, int MOD) {
		long ans = 1;
		while(b>0) {
			if(b%2==0) {
				a *= a;
				a%=MOD;
				b/=2;
			}
			else {
				b-=1;
				ans *= a;
				ans%=MOD;
			}
		}
		return ans;
	}
	public static int[] radixSort(int[] f){ return radixSort(f, f.length); }
	public static int[] radixSort(int[] f, int n)
	{
		int[] to = new int[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]&0xffff]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		return f;
	}
	static int max(int a, int b) { return (a>b)?a:b;}
	
}