#include <bits/stdc++.h>
const long long N = 100100;
const long long Q = 3000100;
const long long mod = 1e9 + 9;
const long long block = sqrt(N);
using namespace std;
long long n, a, b, k;
char c[N];
long long pw(long long x, long long n) {
  if (n == 0) {
    return 1;
  }
  if (n % 2) {
    return x * pw(x, n - 1) % mod;
  } else {
    return pw(x * x % mod, n / 2);
  }
}
vector<vector<long long> > mult(vector<vector<long long> > x,
                                vector<vector<long long> > y) {
  vector<vector<long long> > v;
  v.resize(2);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      v[i].push_back(0);
      for (int h = 0; h < 2; h++) {
        v[i][j] = (v[i][j] + x[i][h] * y[h][j] % mod) % mod;
      }
    }
  }
  return v;
}
vector<vector<long long> > po(vector<vector<long long> > v, long long n) {
  if (n == 1) {
    return v;
  }
  if (n % 2) {
    return mult(v, po(v, n - 1));
  } else {
    return po(mult(v, v), n / 2);
  }
}
void solve() {
  cin >> n >> a >> b >> k;
  long long m = pw(b, k) * pw(pw(a, k), mod - 2) % mod, A = pw(a, mod - 2),
            B = b, f = pw(a, n);
  vector<vector<long long> > tv(2);
  tv[0].resize(2);
  tv[1].resize(2);
  tv[0][0] = 1;
  tv[0][1] = 0;
  tv[1][0] = tv[1][1] = m;
  long long ans = 0;
  for (int i = 0; i < k; i++) {
    cin >> c[i];
    if (c[i] == '+') {
      ans = (ans + f) % mod;
    } else {
      ans = (ans - f) % mod;
      if (ans < 0) {
        ans += mod;
      }
    }
    f = f * A % mod * B % mod;
  }
  vector<vector<long long> > v(2);
  v[0].resize(2);
  v[1].resize(2);
  v[0][0] = v[0][1] = ans;
  v[1][0] = v[1][1] = 0;
  if ((n + 1) / k > 1) {
    v = mult(v, po(tv, (n + 1) / k - 1));
  }
  cout << v[0][0] << "\n";
}
bool mtest = false;
int main() {
  ios_base::sync_with_stdio(0);
  int TE = 1;
  if (mtest) cin >> TE;
  while (TE--) solve();
  return 0;
}

### Prompt

Please create a solution in cpp 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>
const long long N = 100100;
const long long Q = 3000100;
const long long mod = 1e9 + 9;
const long long block = sqrt(N);
using namespace std;
long long n, a, b, k;
char c[N];
long long pw(long long x, long long n) {
  if (n == 0) {
    return 1;
  }
  if (n % 2) {
    return x * pw(x, n - 1) % mod;
  } else {
    return pw(x * x % mod, n / 2);
  }
}
vector<vector<long long> > mult(vector<vector<long long> > x,
                                vector<vector<long long> > y) {
  vector<vector<long long> > v;
  v.resize(2);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      v[i].push_back(0);
      for (int h = 0; h < 2; h++) {
        v[i][j] = (v[i][j] + x[i][h] * y[h][j] % mod) % mod;
      }
    }
  }
  return v;
}
vector<vector<long long> > po(vector<vector<long long> > v, long long n) {
  if (n == 1) {
    return v;
  }
  if (n % 2) {
    return mult(v, po(v, n - 1));
  } else {
    return po(mult(v, v), n / 2);
  }
}
void solve() {
  cin >> n >> a >> b >> k;
  long long m = pw(b, k) * pw(pw(a, k), mod - 2) % mod, A = pw(a, mod - 2),
            B = b, f = pw(a, n);
  vector<vector<long long> > tv(2);
  tv[0].resize(2);
  tv[1].resize(2);
  tv[0][0] = 1;
  tv[0][1] = 0;
  tv[1][0] = tv[1][1] = m;
  long long ans = 0;
  for (int i = 0; i < k; i++) {
    cin >> c[i];
    if (c[i] == '+') {
      ans = (ans + f) % mod;
    } else {
      ans = (ans - f) % mod;
      if (ans < 0) {
        ans += mod;
      }
    }
    f = f * A % mod * B % mod;
  }
  vector<vector<long long> > v(2);
  v[0].resize(2);
  v[1].resize(2);
  v[0][0] = v[0][1] = ans;
  v[1][0] = v[1][1] = 0;
  if ((n + 1) / k > 1) {
    v = mult(v, po(tv, (n + 1) / k - 1));
  }
  cout << v[0][0] << "\n";
}
bool mtest = false;
int main() {
  ios_base::sync_with_stdio(0);
  int TE = 1;
  if (mtest) cin >> TE;
  while (TE--) solve();
  return 0;
}

```