[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 a long long integer mod=1e9+9
into the function qm which takes two long long integers a and b and returns a long long int
    let ans be long long int with ans=1
    while b>0 do the following
        if b&1 then set ans= ans * a % mod
        set b= b >> 1
        set a= a*a%mod
    end of the block
    return (ans % mod + mod) % mod
end of the block
c= character array of size 1000005
define the main function
    n,a,b,k= long long ints
    read n,a,b,k
    read c
    create long long int ans=0
    if n+1 <= k
        for i=0 to n inclusive
            if c[i] = -
                then set ans = ans - qm(a, n - i) * qm(b, i)
                set ans = (ans % mod + mod) % mod
            else do the following
                set ans = ans + qm(a, n - i) * qm(b, i)
                set ans = (ans % mod + mod) % mod
            end of the block
        end of the block
        set ans = (ans % mod + mod) % mod
        print ans
    else do the following
        create long long t= (n+1) / k
        creaye long long integer g = (n+1) %k
        let x=0 be a long long integer
        if g is equal to 0
            for i=0 to k exclusive
                if c[i] is equal to -
                    then set x = x - qm(a, n - i) * qm(b, i)
                    set x = (x % mod + mod) % mod
                else do the following
                    set x = x + qm(a, n - i) * qm(b, i)
                    assign (x % mod + mod) % mod to x
                end of the block
            end of the block
            if qm(a, k) = qm(b, k)
                then set ans = t*t
                assign (ans % mod + mod) % mod to ans
                print ans
                return to indicate successful execution
            end of the block
            create long long integer jj = qm(a, t * k) - qm(b, t * k)
            set jj = x*jj%mod
            set jj= jj* qm(a,k) % mod
            do nothing
            set jj = jj % mod
            create long long integer nn = qm(a, k) - qm(b, k)
            set nn = nn % mod
            assign nn * qm(a, t * k) to nn
            set nn = nn % mod
            set nn = qm(nn, mod - 2)
            assign jj * nn to ans
            set ans to (ans % mod + mod) % mod
            print ans
        else do the following
            for i=0 to k exclusive
                if c[i] is equal to -
                    set x = x - qm(a, n - i) * qm(b, i)
                    set x = (x % mod + mod) % mod
                else do the following
                    set x to x + qm(a, n - i) * qm(b, i)
                    assign (x % mod + mod) % mod to x
                end of the block
            end of the block
            if qm(a, k) == qm(b, k)
                then set ans= t*x
                set ans = (ans % mod + mod) % mod
                for hh=0 to g exclusive
                    if c[hh] is equal to -
                        set ans = ans - qm(a, n - (t * k + hh)) * qm(b, (t * k + hh))
                        set ans = (ans % mod + mod) % mod
                    else do the following
                        set ans = ans + qm(a, n - (t * k + hh)) * qm(b, (t * k + hh))
                        set ans = (ans % mod + mod) % mod
                    end of the block
                end of the block
                set ans = (ans % mod + mod) % mod
                print ans
                return to indicate successful execution
            end of the block
            create long long integer jj = qm(a, t * k) - qm(b, t * k)
            set jj to x * jj % mod
            set jj = jj * qm(a, k) % mod
            do nothing
            assign jj % mod to jj
            create long long integer nn = (qm(a, k) - qm(b, k))
            set nn = nn % mod
            assign nn * qm(a, t * k) to nn
            set nn = nn % mod
            set nn = qm(nn, mod - 2)
            set ans = jj * nn
            set ans = (ans % mod + mod) % mod
            for hh=0 to g exclusive
                if c[hh] is -
                    set ans = ans - qm(a, n - (t * k + hh)) * qm(b, (t * k + hh))
                    set ans = (ans % mod + mod) % mod
                else do the following
                    set ans = ans + qm(a, n - (t * k + hh)) * qm(b, (t * k + hh))
                    set ans = (ans % mod + mod) % mod
                end of the block
            end of the block
            set ans = (ans % mod + mod) % mod
            print ans
        end of the block
    end of the block
end of the block

[CODE]:

long long mod = 1e9 + 9;
long long qm(long long a, long long b) {
    long long ans = 1;
    while (b > 0) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return (ans % mod + mod) % mod;
}
char c[1000005];
int main() {
    long long n, a, b, k;
    cin >> n >> a >> b >> k;
    cin >> c;
    long long ans = 0;
    if (n + 1 <= k) {
        for (long long i = 0; i <= n; i++) {
            if (c[i] == '-') {
                ans = ans - qm(a, n - i) * qm(b, i);
                ans = (ans % mod + mod) % mod;
            } else {
                ans = ans + qm(a, n - i) * qm(b, i);
                ans = (ans % mod + mod) % mod;
            }
        }
        ans = (ans % mod + mod) % mod;
        cout << ans << endl;
    } else {
        long long t = (n + 1) / k;
        long long g = (n + 1) % k;
        long long x = 0;
        if (g == 0) {
            for (long long i = 0; i < k; i++) {
                if (c[i] == '-') {
                    x = x - qm(a, n - i) * qm(b, i);
                    x = (x % mod + mod) % mod;
                } else {
                    x = x + qm(a, n - i) * qm(b, i);
                    x = (x % mod + mod) % mod;
                }
            }
            if (qm(a, k) == qm(b, k)) {
                ans = t * x;
                ans = (ans % mod + mod) % mod;
                cout << ans << endl;
                return 0;
            }
            long long jj = qm(a, t * k) - qm(b, t * k);
            jj = x * jj % mod;
            jj = jj * qm(a, k) % mod;
            ;
            jj = jj % mod;
            long long nn = (qm(a, k) - qm(b, k));
            nn = nn % mod;
            nn = nn * qm(a, t * k);
            nn = nn % mod;
            nn = qm(nn, mod - 2);
            ans = jj * nn;
            ans = (ans % mod + mod) % mod;
            cout << ans << endl;
        } else {
            for (long long i = 0; i < k; i++) {
                if (c[i] == '-') {
                    x = x - qm(a, n - i) * qm(b, i);
                    x = (x % mod + mod) % mod;
                } else {
                    x = x + qm(a, n - i) * qm(b, i);
                    x = (x % mod + mod) % mod;
                }
            }
            if (qm(a, k) == qm(b, k)) {
                ans = t * x;
                ans = (ans % mod + mod) % mod;
                for (long long hh = 0; hh < g; hh++) {
                    if (c[hh] == '-') {
                        ans = ans - qm(a, n - (t * k + hh)) * qm(b, (t * k + hh));
                        ans = (ans % mod + mod) % mod;
                    } else {
                        ans = ans + qm(a, n - (t * k + hh)) * qm(b, (t * k + hh));
                        ans = (ans % mod + mod) % mod;
                    }
                }
                ans = (ans % mod + mod) % mod;
                cout << ans << endl;
                return 0;
            }
            long long jj = qm(a, t * k) - qm(b, t * k);
            jj = x * jj % mod;
            jj = jj * qm(a, k) % mod;
            ;
            jj = jj % mod;
            long long nn = (qm(a, k) - qm(b, k));
            nn = nn % mod;
            nn = nn * qm(a, t * k);
            nn = nn % mod;
            nn = qm(nn, mod - 2);
            ans = jj * nn;
            ans = (ans % mod + mod) % mod;
            for (long long hh = 0; hh < g; hh++) {
                if (c[hh] == '-') {
                    ans = ans - qm(a, n - (t * k + hh)) * qm(b, (t * k + hh));
                    ans = (ans % mod + mod) % mod;
                } else {
                    ans = ans + qm(a, n - (t * k + hh)) * qm(b, (t * k + hh));
                    ans = (ans % mod + mod) % mod;
                }
            }
            ans = (ans % mod + mod) % mod;
            cout << ans << endl;
        }
    }
}