[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 constant integer N = 2e5 + 10
declare long long integers n, a, b, k, MOD = 1e9 + 9
declare fast_power with long longs base, power as arguments, returning long long
    declare long long result = 1
    while power is greater than 0
        if power % 2 is 1, let result be (result * base) % MOD
        let base be (base * base) % MOD
        let power be power / 2
    end of the block
    return result from function
end of the block
define the main function
    read n, a, b, k
    declare string s
    read s
    declare integer l = (n + 1) / k - 1
    declare long long integer val = (b * result of run fast_power(a, MOD - 2)) % MOD
    declare long long integer valp = result of run fast_power(val, k)
    declare long long integer ans = 0
    declare long long integer geo
    if valp is not 1
        let geo be (result of run fast_power(valp, l + 1) - 1) % MOD + MOD
        let geo be geo * result of run fast_power((valp - 1) % MOD + MOD, MOD - 2) % MOD
        let geo be geo % MOD
    else
        let geo be l + 1
    for i = 0 to k exclusive
        declare long long integer calc = result of run fast_power(b, i) * result of run fast_power(a, n - i) % MOD
        if s[i] is '-'
            let ans be (ans - (geo * calc % MOD)) % MOD + MOD
        else
            let ans be (ans + (geo * calc % MOD) % MOD)
        let ans be ans % MOD
    end of the block
    print ans and newline
    return to indicate successful execution
end of the block

[CODE]:

const int N = 2e5 + 10;
long long int n, a, b, k, MOD = 1e9 + 9;
long long fast_power(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power % 2 == 1) { result = (result * base) % MOD; }
        base = (base * base) % MOD;
        power = power / 2;
    }
    return result;
}
int main() {
    cin >> n >> a >> b >> k;
    string s;
    cin >> s;
    int l = (n + 1) / k - 1;
    long long int val = (b * fast_power(a, MOD - 2)) % MOD;
    long long int valp = fast_power(val, k);
    long long int ans = 0;
    long long int geo;
    if (valp != 1) {
        geo = (fast_power(valp, l + 1) - 1) % MOD + MOD;
        geo = geo * fast_power((valp - 1) % MOD + MOD, MOD - 2) % MOD;
        geo %= MOD;
    } else
        geo = l + 1;
    for (int i = 0; i < k; i++) {
        long long int calc = fast_power(b, i) * fast_power(a, n - i) % MOD;
        if (s[i] == '-')
            ans = (ans - (geo * calc % MOD)) % MOD + MOD;
        else
            ans = (ans + (geo * calc % MOD) % MOD);
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}