#include <bits/stdc++.h>
using namespace std;
long long modpow(long long x, long long n, long long M) {
  int result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * x) % M;
    x = (x * x) % M;
    n = n / 2;
  }
  return result;
}
long long invmod(long long a) {
  return (modpow(a, 1000000009 - 2, 1000000009));
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long n, a, b, c, val, ans, t, f, m, q, l, r, k, i, j, x1, x, b1, b2, e,
      x0, w, y, z, p, v, d, u, num;
  cin >> n >> a >> b >> k;
  long long seq;
  string s;
  cin >> s;
  if (a != b) {
    val =
        (modpow(b, n + 1, 1000000009) * invmod(modpow(a, n + 1, 1000000009))) %
        1000000009;
    seq = (1 - val) % 1000000009;
    if (seq < 0) seq += 1000000009;
    val = (1 - (modpow(b, k, 1000000009) * invmod(modpow(a, k, 1000000009))) %
                   1000000009) %
          1000000009;
    if (val == 0) {
      seq = ((n + 1) / (k));
      goto l1;
    }
    if (val < 0) val += 1000000009;
    seq = (seq * invmod(val)) % 1000000009;
  } else {
    seq = ((n + 1) / (k));
  }
l1:;
  ans = 0;
  val = modpow(a, n, 1000000009);
  for (i = 0; i < k; i++) {
    if (s[i] == '+')
      ans = (ans + val) % 1000000009;
    else
      ans = (ans - val) % 1000000009;
    if (ans < 0) ans += 1000000009;
    val = ((val * b) % 1000000009 * invmod(a)) % 1000000009;
  }
  ans = (ans * seq) % 1000000009;
  cout << ans;
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
long long modpow(long long x, long long n, long long M) {
  int result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * x) % M;
    x = (x * x) % M;
    n = n / 2;
  }
  return result;
}
long long invmod(long long a) {
  return (modpow(a, 1000000009 - 2, 1000000009));
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long n, a, b, c, val, ans, t, f, m, q, l, r, k, i, j, x1, x, b1, b2, e,
      x0, w, y, z, p, v, d, u, num;
  cin >> n >> a >> b >> k;
  long long seq;
  string s;
  cin >> s;
  if (a != b) {
    val =
        (modpow(b, n + 1, 1000000009) * invmod(modpow(a, n + 1, 1000000009))) %
        1000000009;
    seq = (1 - val) % 1000000009;
    if (seq < 0) seq += 1000000009;
    val = (1 - (modpow(b, k, 1000000009) * invmod(modpow(a, k, 1000000009))) %
                   1000000009) %
          1000000009;
    if (val == 0) {
      seq = ((n + 1) / (k));
      goto l1;
    }
    if (val < 0) val += 1000000009;
    seq = (seq * invmod(val)) % 1000000009;
  } else {
    seq = ((n + 1) / (k));
  }
l1:;
  ans = 0;
  val = modpow(a, n, 1000000009);
  for (i = 0; i < k; i++) {
    if (s[i] == '+')
      ans = (ans + val) % 1000000009;
    else
      ans = (ans - val) % 1000000009;
    if (ans < 0) ans += 1000000009;
    val = ((val * b) % 1000000009 * invmod(a)) % 1000000009;
  }
  ans = (ans * seq) % 1000000009;
  cout << ans;
  return 0;
}

```