#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1E9 + 9;
const int N = 1E5 + 7;
char s[N];
long long qpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
int main() {
  long long MOD2;
  long long n, a, b, k;
  MOD2 = MOD * MOD;
  assert(MOD2 < LLONG_MAX);
  scanf("%lld %lld %lld %lld", &n, &a, &b, &k);
  scanf("%s", s);
  long long UP = (n + 1) / k;
  if (UP > 1E6) {
    UP = (n + 1) / (k * 1000LL);
    long long rem = (n + 1) % (k * 1000LL);
    long long t(0);
    for (int i = 0; i < (k * 1000LL); i++) {
      long long in1 = qpow(a, n - i);
      long long in2 = qpow(b, i);
      if (s[i % k] == '+')
        t = (t + in1 * in2) % MOD;
      else
        t = (t - in1 * in2 + MOD2) % MOD;
    }
    long long res = t;
    for (int i = 1; i < UP; i++) {
      t = t * qpow(b, (k * 1000LL)) % MOD;
      t = t * qpow(qpow(a, (k * 1000LL)), MOD - 2) % MOD;
      res += t;
      res = (res + MOD2) % MOD;
    }
    t = 0;
    int nowp = 0;
    for (int i = rem - 1; i >= 0; i--) {
      long long in1 = qpow(a, i);
      long long in2 = qpow(b, n - i);
      if (s[nowp] == '+')
        t = (t + in1 * in2) % MOD;
      else
        t = (t - in1 * in2 + MOD2) % MOD;
      ++nowp;
      if (nowp >= k) nowp = 0;
    }
    res = (res + t + MOD2) % MOD;
    return !printf("%lld", res);
  }
  long long t = 0;
  assert(t == 0);
  for (int i = 0; i < k; i++) {
    long long in1 = qpow(a, n - i);
    long long in2 = qpow(b, i);
    if (s[i] == '+')
      t = (t + in1 * in2) % MOD;
    else
      t = (t - in1 * in2 + MOD2) % MOD;
  }
  long long res = t;
  for (int i = 1; i < UP; i++) {
    long long in1 = qpow(b, k);
    long long in2 = qpow(a, k);
    t = t * in1 % MOD;
    t = t * qpow(in2, MOD - 2) % MOD;
    res += t;
    res = (res + MOD2) % MOD;
  }
  return !printf("%lld", res);
}

### Prompt

Please formulate a CPP solution to the following problem:

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}.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1E9 + 9;
const int N = 1E5 + 7;
char s[N];
long long qpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
int main() {
  long long MOD2;
  long long n, a, b, k;
  MOD2 = MOD * MOD;
  assert(MOD2 < LLONG_MAX);
  scanf("%lld %lld %lld %lld", &n, &a, &b, &k);
  scanf("%s", s);
  long long UP = (n + 1) / k;
  if (UP > 1E6) {
    UP = (n + 1) / (k * 1000LL);
    long long rem = (n + 1) % (k * 1000LL);
    long long t(0);
    for (int i = 0; i < (k * 1000LL); i++) {
      long long in1 = qpow(a, n - i);
      long long in2 = qpow(b, i);
      if (s[i % k] == '+')
        t = (t + in1 * in2) % MOD;
      else
        t = (t - in1 * in2 + MOD2) % MOD;
    }
    long long res = t;
    for (int i = 1; i < UP; i++) {
      t = t * qpow(b, (k * 1000LL)) % MOD;
      t = t * qpow(qpow(a, (k * 1000LL)), MOD - 2) % MOD;
      res += t;
      res = (res + MOD2) % MOD;
    }
    t = 0;
    int nowp = 0;
    for (int i = rem - 1; i >= 0; i--) {
      long long in1 = qpow(a, i);
      long long in2 = qpow(b, n - i);
      if (s[nowp] == '+')
        t = (t + in1 * in2) % MOD;
      else
        t = (t - in1 * in2 + MOD2) % MOD;
      ++nowp;
      if (nowp >= k) nowp = 0;
    }
    res = (res + t + MOD2) % MOD;
    return !printf("%lld", res);
  }
  long long t = 0;
  assert(t == 0);
  for (int i = 0; i < k; i++) {
    long long in1 = qpow(a, n - i);
    long long in2 = qpow(b, i);
    if (s[i] == '+')
      t = (t + in1 * in2) % MOD;
    else
      t = (t - in1 * in2 + MOD2) % MOD;
  }
  long long res = t;
  for (int i = 1; i < UP; i++) {
    long long in1 = qpow(b, k);
    long long in2 = qpow(a, k);
    t = t * in1 % MOD;
    t = t * qpow(in2, MOD - 2) % MOD;
    res += t;
    res = (res + MOD2) % MOD;
  }
  return !printf("%lld", res);
}

```