[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]:
declare long long MOD = 1000000009
declare pw with long longs a, b as arguments, returning long long
    if b is 0, return 1 from function
    if b is 1, return a % MOD
    if b % 2
        declare long long rs = result of run pw ( a, b - 1 )
        return ( rs * a ) % MOD from function
    end of the block
    declare long long rs = result of run w with a, b / 2 as arguments
    return ( rs * rs ) % MOD
end of the block
declare long long vector sm
declare solve with long longs a, b as arguments, returning long long
    if b is 0, return 0 from function
    for i = 0 to 35 exclusive
        declare long long ba = (1LL bitshift left i ) bitwise and b
        if ba is 0, end current loop iteration
        return ( sm[i] + result of run solve( a, b - ( 1LL bitshift left i )) * result of run pw(a, (1LL bitshift left i))) % MOD
    end of the block
end of the block
define the main function
    declare long longs n, a, b, k
    read n, a, b, k
    declare string s
    read s
    declare long long X = 1, y + 1
    for i = 0 to k exclusive
        let X be X * b
        let X be X % MOD
    end of the block
    for i = 0 to k exclusive
        let Y be Y * a
        let Y be Y % MOD
    end of the block
    let X be X * result of run pw(Y, MOD - 2)
    let X be X % MOD
    add 1 to end of sm
    for i = 0 to 40 exclusive
        add ( back of sm + back of sm * result of run pw(X, (1LL bitshift left i) ) to end of sm
        let back of sm be back of sm % MOD
    end of the block
    declare long long st = result of run solve(X, (n + 1) / k)
    declare long long ans = 0
    for i = 0 to k exclusive
        declare long long rs = (result of run pw(b,i) * result of run pw(a,n-1) ) % MOD
        if s[i] is '-', let rs be rs * -1
        let rs be rs * st
        increment ans by rs
        let ans be ans % MOD
    end of the block
    if ans is less than 0, increment ans by MOD
    print ans and newline
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;
}