[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
MAXN = constant integer = 100000
MOD = constant long long = 1000000009
in function poww_mod with arguments long long a and long long b that returns long long
    ans = long long = 1
    a = a modulo MOD
    while b is nonzero
        if b ends in a one in bits, then ans = (a * ans) modulo MOD
        a = (a * a) modulo MOD
        b shifted by one bit to the right
    end of the block
    return ans modulo MOD
end of the block
in function inv with arguments of long long t and long long p that returns a long long
    t = t modulo p
    return 1 if t is 1 else return (p - p / t) * (call inv with arguments of p modulo t and p) modulo p
end of the block
n = integer = 0, k = integer = 0, a = integer = 0, b = integer = 0
ans = long long array of size MAX + 5, answer = long long = 0
s = string
define the main function
    read n, a, b, k
    read s
    pre = long long = 0
    while k < 10000 and k < n
        k = k * 2
        s = s + s
    end of the block
    for i = 0 to k exclusive
        if s[i] is +
            ans[i] = pre + (call poww_mod with arguments of a, n - i) * (call poww_mod with arguments of b, i) modulo MOD
        else
            ans[i] = pre - (call poww_mod with arguments of a, n - i) * (call poww_mod with arguments of b, i) modulo MOD
        pre = ans[i]
    end of the block
    if n < k
        if ans[n] < 0, then ans[n] = ans[n] + mod
        print ans[n]
    else
        beishu = integer = n / k
        save = integer = n - n / k
        mode = long long =(call poww_mod with arguments of b, k) * (inverse of arguments of (the result of calling poww_mod with arguments of a, k), i) MOD )modulo MOD
        answer = pre
        for i = 1 to beishu exclusive
            pre = (pre * mode) modulo MOD
            answer = (answer + pre) modulo MOD
        end of the block
        for i = n / k * k to n inclusive
            if s[i modulo k] is +
                answer = (answer + (call poww_mod with arguments of a, n - i) * (call poww_mod with arguments of b, i)) modulo MOD
            else
                answer = (answer - (call poww_mod with arguments of a, n - i) * (call poww_mod with arguments of b, i)) modulo MOD
        end of the block
        if answer < 0, then answer = answer + MOD
        print answer
    end of the block
end of the block

[CODE]:

const int MAXN = 100000;
const long long MOD = 1000000009;
long long poww_mod(long long a, long long b) {
    long long ans = 1;
    a = a % MOD;
    while (b) {
        if (b & 1) ans = (a * ans) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ans % MOD;
}
long long inv(long long t, long long p) {
    t = t % p;
    return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
}
int n = 0, k = 0, a = 0, b = 0;
long long ans[MAXN + 5], answer = 0;
string s;
int main() {
    cin >> n >> a >> b >> k;
    cin >> s;
    long long pre = 0;
    while (k < 10000 && k < n) {
        k = k * 2;
        s = s + s;
    }
    for (int i = 0; i < k; ++i) {
        if (s[i] == '+')
            ans[i] = (pre + poww_mod(a, n - i) * poww_mod(b, i)) % MOD;
        else
            ans[i] = (pre - poww_mod(a, n - i) * poww_mod(b, i)) % MOD;
        pre = ans[i];
    }
    if (n < k) {
        if (ans[n] < 0) ans[n] += MOD;
        cout << ans[n] << endl;
    } else {
        int beishu = n / k;
        int save = n - n / k;
        long long mode = (poww_mod(b, k) * inv(poww_mod(a, k), MOD)) % MOD;
        answer = pre;
        for (int i = 1; i < beishu; ++i) {
            pre = (pre * mode) % MOD;
            answer = (answer + pre) % MOD;
        }
        for (int i = (n / k) * k; i <= n; ++i) {
            if (s[i % k] == '+')
                answer = (answer + poww_mod(a, n - i) * poww_mod(b, i)) % MOD;
            else
                answer = (answer - poww_mod(a, n - i) * poww_mod(b, i)) % MOD;
        }
        if (answer < 0) answer += MOD;
        cout << answer << endl;
    }
}