[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 const long long integer mod = 1e9 + 9
declare mod_pow taking in long long ints x and n and returning long long integer
    make long long res = 1
    while n is greater than 0
        if n & 1 is truthy, set res to res * x % mod
        set x to x * x % mod
        move bits of n 1 place to right
    end of the block
    return res
end of the block
declare extgcd taking in long long ints a, b, &x, and &y and returning long long integer
    make long long int d = a
    if b is not 0
        set d to extgcd(b, a % b, y, x)
        set y to y - (a / b) * x
    else do
        set x to 1
        set y to 0
    end of the block
    return d
end of the block
declare mod_inverse taking in long long a and returning long long int
    create long long ints x, y, and m
    set m to mod
    call extgcd(a, m, x, y)
    return the result of (m + x % m) % m
end of the block
define the main function
    make long long ints n, a, b, k, ans, temp, rec, and q
    make string s
    read n, a, b, and k
    read s
    set ans to 0
    for i = 0 to k exclusive
        set temp to (mod_pow(a, n - i) * mod_pow(b, i)) % mod
        if s[i] is equal to '+'
            set ans to (ans + temp) % mod
        else do
            set ans to (ans - temp) % mod
        if ans is less than 0, set ans to ans + mod
    end of the block
    if n + 1 is k
        print ans
        return to indicate successful execution
    end of the block
    set rec to (n + 1) / k
    set q to mod_pow((mod_inverse(a) * b) % mod, k) % mod
    if q is equal to 1
        set ans to (ans * rec) % mod
    otherwise
        set ans to ((ans * (mod_pow(q, rec) - 1) % mod) * mod_inverse(q - 1)) % mod
    display ans
    return to indicate successful execution
end of the block

[CODE]:

const long long mod = 1e9 + 9;
long long mod_pow(long long x, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
long long extgcd(long long a, long long b, long long &x, long long &y) {
    long long d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}
long long mod_inverse(long long a) {
    long long x, y, m;
    m = mod;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
int main() {
    long long n, a, b, k, ans, temp, rec, q;
    string s;
    cin >> n >> a >> b >> k;
    cin >> s;
    ans = 0;
    for (int i = 0; i < k; i++) {
        temp = (mod_pow(a, n - i) * mod_pow(b, i)) % mod;
        if (s[i] == '+')
            ans = (ans + temp) % mod;
        else
            ans = (ans - temp) % mod;
        if (ans < 0) ans += mod;
    }
    if (n + 1 == k) {
        cout << ans << endl;
        return 0;
    }
    rec = (n + 1) / k;
    q = mod_pow((mod_inverse(a) * b) % mod, k) % mod;
    if (q == 1)
        ans = (ans * rec) % mod;
    else
        ans = ((ans * (mod_pow(q, rec) - 1) % mod) * mod_inverse(q - 1)) % mod;
    cout << ans << endl;
    return 0;
}