[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 long long int mod = 1e9 + 9
create ints d, x, and y
declare fastexp taking in long long ints b and p and returning long long integer
    if p is 0, return 1
    create long long int ans = fastexp(b, p / 2) % mod
    if p modulo 2 is truthy
        return the result of ((1LL * b * ans % mod) * 1LL * ans) % mod
    else do
        return the result of (1LL * ans * ans + mod) % mod
end of the block
define the main function
    make long long ints a, n, b, and k
    create string s
    make long long integers v1, v2, v3, and sum = 0
    read n, a, b, and k
    read s
    for h = 0 to k exclusive
        if s[h] equals '+'
            set v1 to fastexp(a, n - h) % mod
            set v2 to fastexp(b, h) % mod
            set v3 to (v1 * v2 + mod) % mod
            set sum to (sum % mod + v3 % mod + mod) % mod
        else do
            set v1 to fastexp(a, n - h)
            set v2 to return value of fastexp(b, h)
            set v3 to (v1 * v2 + mod) % mod
            set sum to (sum % mod - v3 % mod + mod) % mod
        end of the block
    end of the block
    create long long int v1 = (n + 1) / k
    make long long integer inv_a = fastexp(a, mod - 2) % mod
    make long long integer vv = ((inv_a % mod) * (b % mod) + mod) % mod
    let long long integer vl1 = ((fastexp(vv, k) % mod)) % mod
    if vl1 is 1
        create long long int ans = ((v1 * sum) + mod) % mod
        display ans
        return to indicate successful execution
    end of the block
    create long long integer vl4 = fastexp(vl1, vl) % mod
    set vl4 to (vl4 - 1 + mod) % mod
    set vl4 to (vl4 * sum + mod) % mod
    make long long integer vl2 = (((vl1 + mod) % mod) - 1 + mod) % mod
    create long long integer vl3 = (vl4 * (fastexp(vl2, mod - 2)) + mod) % mod
    print the result of vl3 % mod
end of the block

[CODE]:

long long int mod = 1e9 + 9;
int d, x, y;
long long int fastexp(long long int b, long long int p) {
    if (p == 0) return 1;
    long long int ans = fastexp(b, p / 2) % mod;
    if (p % 2)
        return ((1LL * b * ans % mod) * 1LL * ans) % mod;
    else
        return (1LL * ans * ans + mod) % mod;
}
int main() {
    long long int a, n, b, k;
    string s;
    long long int v1, v2, v3, sum = 0;
    cin >> n >> a >> b >> k;
    cin >> s;
    for (int h = 0; h < k; h++) {
        if (s[h] == '+') {
            v1 = fastexp(a, n - h) % mod;
            v2 = fastexp(b, h) % mod;
            v3 = (v1 * v2 + mod) % mod;
            sum = (sum % mod + v3 % mod + mod) % mod;
        } else {
            v1 = fastexp(a, n - h);
            v2 = fastexp(b, h);
            v3 = (v1 * v2 + mod) % mod;
            sum = (sum % mod - v3 % mod + mod) % mod;
        }
    }
    long long int vl = (n + 1) / k;
    long long int inv_a = fastexp(a, mod - 2) % mod;
    long long int vv = ((inv_a % mod) * (b % mod) + mod) % mod;
    long long int vl1 = ((fastexp(vv, k) % mod)) % mod;
    if (vl1 == 1) {
        long long int ans = ((vl * sum) + mod) % mod;
        cout << ans << endl;
        return 0;
    }
    long long int vl4 = fastexp(vl1, vl) % mod;
    vl4 = (vl4 - 1 + mod) % mod;
    vl4 = (vl4 * sum + mod) % mod;
    long long int vl2 = (((vl1 + mod) % mod) - 1 + mod) % mod;
    long long int vl3 = (vl4 * (fastexp(vl2, mod - 2)) + mod) % mod;
    cout << vl3 % mod << endl;
}