#include <bits/stdc++.h>
using namespace std;
const int INFL = (int)1e9;
const long long int INFLL = (long long int)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
namespace mod_op {
const long long int MOD = (long long int)1e9 + 9;
class Extended_Euclid {
 private:
  long long int m, n;
  vector<vector<long long int>> mx_multiply(vector<vector<long long int>> mx1,
                                            vector<vector<long long int>> mx2) {
    vector<vector<long long int>> ret(mx1.size(),
                                      vector<long long int>(mx2[0].size(), 0));
    for (int i = 0; i < (int)mx1.size(); i++) {
      for (int j = 0; j < (int)mx1[0].size(); j++) {
        for (int k = 0; k < (int)mx2[0].size(); k++) {
          ret[i][j] += mx1[i][k] * mx2[k][j];
        }
      }
    }
    return ret;
  }

 public:
  long long int x, y, gcd;
  Extended_Euclid(long long int M, long long int N) {
    m = M;
    n = N;
    vector<long long int> r(100), k(100);
    bool swapflag = false, m_negflag = false, n_negflag = false;
    if (m < n) {
      swap(m, n);
      swapflag = true;
    }
    if (m < 0) {
      m *= -1;
      m_negflag = true;
    }
    if (n < 0) {
      n *= -1;
      n_negflag = true;
    }
    r[0] = m;
    r[1] = n;
    int h = 1;
    while (1) {
      k[h - 1] = r[h - 1] / r[h];
      r[h + 1] = r[h - 1] % r[h];
      if (r[h + 1] == 0) break;
      h++;
    }
    gcd = r[h];
    vector<vector<long long int>> mx1 = {{0, 1}, {1, (-1) * k[h - 1]}};
    for (int i = (int)h - 1 - 1; i >= 0; i--) {
      vector<vector<long long int>> mx2 = {{0, 1}, {1, (-1) * k[i]}};
      mx1 = mx_multiply(mx1, mx2);
    }
    x = mx1[0][0];
    y = mx1[0][1];
    if (n_negflag) {
      n *= -1;
      y *= -1;
    }
    if (m_negflag) {
      m *= -1;
      x *= -1;
    }
    if (swapflag) {
      swap(m, n);
      swap(x, y);
    }
  }
};
class modll {
 private:
  long long int mod;
  long long int val;
  inline long long int modify(long long int x) {
    return x - (x >= 0 ? x : (x - mod + 1)) / mod * mod;
  }
  inline long long int inv(long long int x) {
    Extended_Euclid ee(x, -mod);
    return modify(ee.x);
  }

 public:
  modll(long long int init = 0, long long int mod = MOD) {
    modll::mod = mod;
    val = modify(init);
    return;
  }
  modll(const modll &another) {
    *this = another;
    return;
  }
  inline operator long long int() { return val; }
  inline modll &operator=(const long long int &x) {
    val = modify(x);
    return *this;
  }
  inline modll operator+(const long long int &x) {
    modll ret;
    ret = modify(val + x);
    return ret;
  }
  inline modll operator-(const long long int &x) {
    modll ret;
    ret = modify(val - x);
    return ret;
  }
  inline modll operator*(const long long int &x) {
    modll ret;
    ret = modify(val * x);
    return ret;
  }
  inline modll operator/(const long long int &x) {
    modll ret;
    ret = modify(val * inv(x));
    return ret;
  }
  inline modll &operator+=(const long long int &x) {
    val = modify(val + x);
    return *this;
  }
  inline modll &operator-=(const long long int &x) {
    val = modify(val - x);
    return *this;
  }
  inline modll &operator*=(const long long int &x) {
    val = modify(val * x);
    return *this;
  }
  inline modll &operator/=(const long long int &x) {
    val = modify(val * inv(x));
    return *this;
  }
  friend inline istream &operator>>(istream &is, modll &x) {
    is >> x.val;
    return is;
  }
  long long int get_mod() { return mod; }
};
modll pow(modll n, long long int p) {
  modll ret;
  if (p == 0)
    ret = 1;
  else if (p == 1)
    ret = n;
  else {
    ret = pow(n, p / 2);
    ret *= ret;
    if (p % 2 == 1) ret *= n;
  }
  return ret;
}
vector<modll> facts;
void make_facts(int n) {
  if (facts.empty()) facts.push_back(modll(1));
  for (int i = facts.size(); i <= n; ++i)
    facts.push_back(modll(facts.back() * (long long int)i));
  return;
}
modll combination(modll n, long long int r) {
  modll ret;
  make_facts((int)n);
  ret = facts[(unsigned)n] / (facts[(unsigned)r] * facts[(unsigned)(n - r)]);
  return ret;
}
long long int disc_log(modll a, modll b) {
  long long int ret = -1;
  long long int m = ((long long int)sqrt((double)a.get_mod()) +
                     ((long long int)a.get_mod() <=
                              (long long int)sqrt((double)a.get_mod()) *
                                  (long long int)sqrt((double)a.get_mod())
                          ? 0
                          : 1));
  unordered_map<long long int, long long int> mp;
  modll x = 1;
  for (int i = 0; i < (int)m; i++) {
    mp[x] = i;
    x *= a;
  }
  x = 1 / pow(a, m);
  modll k = b;
  for (int i = 0; i < (int)m; i++) {
    if (mp.find(k) == mp.end()) k *= x;
    ret = i * m + mp[k];
  }
  return ret;
}
}  // namespace mod_op
using namespace mod_op;
int main() {
  long long int n;
  cin >> n;
  modll a, b;
  cin >> a >> b;
  long long int k;
  cin >> k;
  string s;
  cin >> s;
  modll ans = 0;
  modll buf = pow(a, n);
  modll x = b / a;
  for (int i = 0; i < (int)k; i++) {
    if (s[i] == '+')
      ans += buf;
    else
      ans -= buf;
    buf *= x;
  }
  buf = pow(x, k);
  if (buf != 1)
    ans = (ans * pow(buf, (n + 1) / k) - ans) / (buf - 1LL);
  else
    ans *= (n + 1) / k;
  cout << ans << endl;
}

### Prompt

In cpp, your task is to solve 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 INFL = (int)1e9;
const long long int INFLL = (long long int)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
namespace mod_op {
const long long int MOD = (long long int)1e9 + 9;
class Extended_Euclid {
 private:
  long long int m, n;
  vector<vector<long long int>> mx_multiply(vector<vector<long long int>> mx1,
                                            vector<vector<long long int>> mx2) {
    vector<vector<long long int>> ret(mx1.size(),
                                      vector<long long int>(mx2[0].size(), 0));
    for (int i = 0; i < (int)mx1.size(); i++) {
      for (int j = 0; j < (int)mx1[0].size(); j++) {
        for (int k = 0; k < (int)mx2[0].size(); k++) {
          ret[i][j] += mx1[i][k] * mx2[k][j];
        }
      }
    }
    return ret;
  }

 public:
  long long int x, y, gcd;
  Extended_Euclid(long long int M, long long int N) {
    m = M;
    n = N;
    vector<long long int> r(100), k(100);
    bool swapflag = false, m_negflag = false, n_negflag = false;
    if (m < n) {
      swap(m, n);
      swapflag = true;
    }
    if (m < 0) {
      m *= -1;
      m_negflag = true;
    }
    if (n < 0) {
      n *= -1;
      n_negflag = true;
    }
    r[0] = m;
    r[1] = n;
    int h = 1;
    while (1) {
      k[h - 1] = r[h - 1] / r[h];
      r[h + 1] = r[h - 1] % r[h];
      if (r[h + 1] == 0) break;
      h++;
    }
    gcd = r[h];
    vector<vector<long long int>> mx1 = {{0, 1}, {1, (-1) * k[h - 1]}};
    for (int i = (int)h - 1 - 1; i >= 0; i--) {
      vector<vector<long long int>> mx2 = {{0, 1}, {1, (-1) * k[i]}};
      mx1 = mx_multiply(mx1, mx2);
    }
    x = mx1[0][0];
    y = mx1[0][1];
    if (n_negflag) {
      n *= -1;
      y *= -1;
    }
    if (m_negflag) {
      m *= -1;
      x *= -1;
    }
    if (swapflag) {
      swap(m, n);
      swap(x, y);
    }
  }
};
class modll {
 private:
  long long int mod;
  long long int val;
  inline long long int modify(long long int x) {
    return x - (x >= 0 ? x : (x - mod + 1)) / mod * mod;
  }
  inline long long int inv(long long int x) {
    Extended_Euclid ee(x, -mod);
    return modify(ee.x);
  }

 public:
  modll(long long int init = 0, long long int mod = MOD) {
    modll::mod = mod;
    val = modify(init);
    return;
  }
  modll(const modll &another) {
    *this = another;
    return;
  }
  inline operator long long int() { return val; }
  inline modll &operator=(const long long int &x) {
    val = modify(x);
    return *this;
  }
  inline modll operator+(const long long int &x) {
    modll ret;
    ret = modify(val + x);
    return ret;
  }
  inline modll operator-(const long long int &x) {
    modll ret;
    ret = modify(val - x);
    return ret;
  }
  inline modll operator*(const long long int &x) {
    modll ret;
    ret = modify(val * x);
    return ret;
  }
  inline modll operator/(const long long int &x) {
    modll ret;
    ret = modify(val * inv(x));
    return ret;
  }
  inline modll &operator+=(const long long int &x) {
    val = modify(val + x);
    return *this;
  }
  inline modll &operator-=(const long long int &x) {
    val = modify(val - x);
    return *this;
  }
  inline modll &operator*=(const long long int &x) {
    val = modify(val * x);
    return *this;
  }
  inline modll &operator/=(const long long int &x) {
    val = modify(val * inv(x));
    return *this;
  }
  friend inline istream &operator>>(istream &is, modll &x) {
    is >> x.val;
    return is;
  }
  long long int get_mod() { return mod; }
};
modll pow(modll n, long long int p) {
  modll ret;
  if (p == 0)
    ret = 1;
  else if (p == 1)
    ret = n;
  else {
    ret = pow(n, p / 2);
    ret *= ret;
    if (p % 2 == 1) ret *= n;
  }
  return ret;
}
vector<modll> facts;
void make_facts(int n) {
  if (facts.empty()) facts.push_back(modll(1));
  for (int i = facts.size(); i <= n; ++i)
    facts.push_back(modll(facts.back() * (long long int)i));
  return;
}
modll combination(modll n, long long int r) {
  modll ret;
  make_facts((int)n);
  ret = facts[(unsigned)n] / (facts[(unsigned)r] * facts[(unsigned)(n - r)]);
  return ret;
}
long long int disc_log(modll a, modll b) {
  long long int ret = -1;
  long long int m = ((long long int)sqrt((double)a.get_mod()) +
                     ((long long int)a.get_mod() <=
                              (long long int)sqrt((double)a.get_mod()) *
                                  (long long int)sqrt((double)a.get_mod())
                          ? 0
                          : 1));
  unordered_map<long long int, long long int> mp;
  modll x = 1;
  for (int i = 0; i < (int)m; i++) {
    mp[x] = i;
    x *= a;
  }
  x = 1 / pow(a, m);
  modll k = b;
  for (int i = 0; i < (int)m; i++) {
    if (mp.find(k) == mp.end()) k *= x;
    ret = i * m + mp[k];
  }
  return ret;
}
}  // namespace mod_op
using namespace mod_op;
int main() {
  long long int n;
  cin >> n;
  modll a, b;
  cin >> a >> b;
  long long int k;
  cin >> k;
  string s;
  cin >> s;
  modll ans = 0;
  modll buf = pow(a, n);
  modll x = b / a;
  for (int i = 0; i < (int)k; i++) {
    if (s[i] == '+')
      ans += buf;
    else
      ans -= buf;
    buf *= x;
  }
  buf = pow(x, k);
  if (buf != 1)
    ans = (ans * pow(buf, (n + 1) / k) - ans) / (buf - 1LL);
  else
    ans *= (n + 1) / k;
  cout << ans << endl;
}

```