[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]:
create long long integer MOD = 1000000009
into the function pw which takes two long long integers a and b and returns a long long integer
    if b is 0 then return 1
    if b is 1 then return a % MOD
    if b%2 is true
        create long long rs= pw(a,b-1)
        return (rs * a) % MOD
    end of the block
    create long long integer rs= pw(a,b/2)
    return (rs * rs) % MOD
end of the block
sm = long long integer vector
into the function solve which takes a and b
    if b is 0 then return 0
    for i=0 to 35 exclusive
        create long long integer ba = (1LL << i) & b
        if ba is equal to 0 then continue
        return sm[i] + solve(a, b - (1LL << i)) * pw(a, (1LL << i))) % MOD
    end of the block
end of the block
define the main function
    n,a,b,k = long long integers
    read n,a,b,k
    s=string
    read s
    create long long integers X and Y with values 1
    for i=o to k exclusive
        set X = X * b
        set X = X % MOD
    end of the block
    for i=0 to k exclusive
        set Y = Y * a
        set Y = Y % MOD
    end of the block
    set X = X * pw(Y, MOD - 2)
    set X = X % MOD
    add 1 to the end of sm
    for i=0 to 40 exclusive
        add sm.back() + sm.back() * pw(X, (1LL << i) to end of sm
        set sm.back() = sm.back() % MOD
    end of the block
    create long long integer st = solve(X, (n + 1) / k)
    create long long integer ans=0
    for i=0 to k exclusive
        create long long integer rs = (pw(b, i) * pw(a, n - i)) % MOD
        if s[i] is '-' then set rs = rs * -1
        set rs = rs * st
        set ans = ans + rs
        set ans = ans % MOD
    end of the block
    if ans is less than 0 then set ans = ans + MOD
    print ans
end of the block

[CODE]:

long long MOD = 1000000009;
long long pw(long long a, long long b) {
    if (b == 0) return 1;
    if (b == 1) return a % MOD;
    if (b % 2) {
        long long rs = pw(a, b - 1);
        return (rs * a) % MOD;
    }
    long long rs = pw(a, b / 2);
    return (rs * rs) % MOD;
}
vector<long long> sm;
long long solve(long long a, long long b) {
    if (b == 0) return 0;
    for (long long i = 0; i < 35; i++) {
        long long ba = (1LL << i) & b;
        if (ba == 0) continue;
        return (sm[i] + solve(a, b - (1LL << i)) * pw(a, (1LL << i))) % MOD;
    }
}
int main() {
    long long n, a, b, k;
    cin >> n >> a >> b >> k;
    string s;
    cin >> s;
    long long X = 1, Y = 1;
    for (long long i = 0; i < k; i++) {
        X *= b;
        X %= MOD;
    }
    for (long long i = 0; i < k; i++) {
        Y *= a;
        Y %= MOD;
    }
    X *= pw(Y, MOD - 2);
    X %= MOD;
    sm.push_back(1);
    for (long long i = 0; i < 40; i++) {
        sm.push_back(sm.back() + sm.back() * pw(X, (1LL << i)));
        sm.back() %= MOD;
    }
    long long st = solve(X, (n + 1) / k);
    long long ans = 0;
    for (long long i = 0; i < k; i++) {
        long long rs = (pw(b, i) * pw(a, n - i)) % MOD;
        if (s[i] == '-') rs *= -1;
        rs *= st;
        ans += rs;
        ans %= MOD;
    }
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}