#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int P = 1000000009;
int n, a, b, k;
long long ans = 0, part;
char s[N];
void exGcd(int a, int b, int& x, int& y);
int rev(int a);
int mpow(int x, int k);
int main() {
  scanf("%d%d%d%d", &n, &a, &b, &k);
  scanf("%s", s);
  long long ra = rev(a), rb = rev(b), an = mpow(a, n), bn = 1;
  for (int i = 0; i < k; ++i) {
    if (s[i] == '+')
      part = (part + (long long)an * bn) % P;
    else
      part = (part + (long long)(P - 1) * an % P * bn % P) % P;
    an = (long long)an * ra % P;
    bn = (long long)bn * b % P;
  }
  long long cyc = (n + 1) / k;
  long long rat = (long long)mpow(ra, k) * mpow(b, k) % P;
  if (rat != 1)
    ans = part * (long long)(1 + P - (long long)mpow(rat, cyc)) % P *
          rev((1 + P - (long long)rat) % P) % P;
  else
    ans = part * (long long)cyc % P;
  if (ans < 0) ans += P;
  printf("%I64d\n", ans);
  return 0;
}
int mpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = (long long)ret * x % P;
    x = (long long)x * x % P;
    k >>= 1;
  }
  return ret;
}
int rev(int a) {
  int x, y;
  exGcd(a, P, x, y);
  if (x < 0) x += P;
  return x;
}
void exGcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}

### 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 int N = 100010;
const int P = 1000000009;
int n, a, b, k;
long long ans = 0, part;
char s[N];
void exGcd(int a, int b, int& x, int& y);
int rev(int a);
int mpow(int x, int k);
int main() {
  scanf("%d%d%d%d", &n, &a, &b, &k);
  scanf("%s", s);
  long long ra = rev(a), rb = rev(b), an = mpow(a, n), bn = 1;
  for (int i = 0; i < k; ++i) {
    if (s[i] == '+')
      part = (part + (long long)an * bn) % P;
    else
      part = (part + (long long)(P - 1) * an % P * bn % P) % P;
    an = (long long)an * ra % P;
    bn = (long long)bn * b % P;
  }
  long long cyc = (n + 1) / k;
  long long rat = (long long)mpow(ra, k) * mpow(b, k) % P;
  if (rat != 1)
    ans = part * (long long)(1 + P - (long long)mpow(rat, cyc)) % P *
          rev((1 + P - (long long)rat) % P) % P;
  else
    ans = part * (long long)cyc % P;
  if (ans < 0) ans += P;
  printf("%I64d\n", ans);
  return 0;
}
int mpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = (long long)ret * x % P;
    x = (long long)x * x % P;
    k >>= 1;
  }
  return ret;
}
int rev(int a) {
  int x, y;
  exGcd(a, P, x, y);
  if (x < 0) x += P;
  return x;
}
void exGcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}

```