[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]:
make ints n, a, b, and k
let int array s of size 100000
let string inp
make map dp from ints and ints
declare bpow taking in ints n and e and returning integer
    create integer array b of size 30
    set b[0] to n
    for i = 1 to 30 exclusive, set b[i] to ((long long)b[i - 1] * b[i - 1]) % 1000000009
    make integer ans = 1
    for i = 0 to 30 exclusive
        if e & (1 << i) are truthy set ans to ((long long)ans * b[i]) % 1000000009
    return ans
end of the block
declare bdiv taking in integers n and d and returning integer
    return the result of ((long long)n * bpow(d, 1000000009 - 2)) % 1000000009
end of the block
declare alt taking in int e and returning int
    if e % k is not 0, end function
    if dp.count(e) is falsy
        if e is 0
            end function
        else if e is k
            set dp[e] to 1
        else do
            create int l = e / 2 / k * k
            make integer r = e - 1
            let integer ans = (((long long)alt(l) * bpow(a, r)) + (long long)alt(r) * bpow(b, l)) % 1000000009
            set dp[e] to ans
        end of the block
    end of the block
    return dp[e]
end of the block
define the main function
    read n, a, b, and k
    read inp
    for i = 0 to k exclusive
        if inp[i] is '+'
            set s[i] to 1
        else do
            set s[i] to -1
    end of the block
    create int x = 0
    for i = 0 to k exclusive
        create integer toadd = ((long long)s[i] * bpow(a, k - 1 - i)) % 1000000009
        set toadd to ((long long)toadd * bpow(b, i)) % 1000000009
        set x to ((long long)x + toadd + 1000000009) % 1000000009
    end of the block
    display x, " ", and alt(n + 1) to error
    create integer ans = ((long long)x * alt(n + 1)) % 1000000009
    display ans
end of the block

[CODE]:

int n, a, b, k;
int s[100000];
string inp;
map<int, int> dp;
int bpow(int n, int e) {
    int b[30];
    b[0] = n;
    for (int i = 1; i < 30; i++) b[i] = ((long long)b[i - 1] * b[i - 1]) % 1000000009;
    int ans = 1;
    for (int i = 0; i < 30; i++)
        if (e & (1 << i)) ans = ((long long)ans * b[i]) % 1000000009;
    return ans;
}
int bdiv(int n, int d) {
    return ((long long)n * bpow(d, 1000000009 - 2)) % 1000000009;
}
int alt(int e) {
    assert(e % k == 0);
    if (!dp.count(e)) {
        if (e == 0)
            assert(0);
        else if (e == k)
            dp[e] = 1;
        else {
            int l = e / 2 / k * k;
            int r = e - l;
            int ans = (((long long)alt(l) * bpow(a, r)) + (long long)alt(r) * bpow(b, l)) % 1000000009;
            dp[e] = ans;
        }
    }
    return dp[e];
}
int main() {
    cin >> n >> a >> b >> k;
    cin >> inp;
    for (int i = 0; i < k; i++) {
        if (inp[i] == '+')
            s[i] = 1;
        else
            s[i] = -1;
    }
    int x = 0;
    for (int i = 0; i < k; i++) {
        int toadd = ((long long)s[i] * bpow(a, k - 1 - i)) % 1000000009;
        toadd = ((long long)toadd * bpow(b, i)) % 1000000009;
        x = ((long long)x + toadd + 1000000009) % 1000000009;
    }
    cerr << x << " " << alt(n + 1) << endl;
    int ans = ((long long)x * alt(n + 1)) % 1000000009;
    cout << ans << endl;
}