题意

给你一个序列 ，已知序列 的周期是 ，要么要么， 接着也给你两个数和，让你求

思路

我们将提取出来，原式变成 ，那么我们只要能求解就能得到答案，因为的周期为，我们可以将该式子展开，可以得到如下：

不然发现这个是个等比数列，倍数等于，求解完毕

注意事项

注意为的情况不适用于等比求和公式

代码

/**
 *    author: andif
 *    created: 06.08.2023 20:04:55
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;
const int mod = 1e9 + 9;

int get_phi(int x) {
    int ret = 1;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ret *= (i - 1);
            x /= i;
            while(x % i == 0) {
                x /= i;
                ret *= i;
            }
        }
    }
    if (x != 1) ret *= (x - 1);
    return ret;
}

int qpow(int a, int b) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            // dd(a), de(ret);
            ret = 1ll * ret * a % mod;
        }
        a = (1ll * a * a) % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    string s; cin >> s;
    int phi = get_phi(mod);
    // dd(n), dd(a), dd(b), dd(k), dd(s), de(mod);
    int c = qpow(a, phi - 1);
    // de(c);
    int t1 = 0;
    rep(i, 0, k) {
        int si = s[i] == '+' ? 1 : -1;
        t1 = (t1 + 1ll * si * qpow(c, i) % mod * qpow(b, i) % mod) % mod;
        if (t1 < 0) t1 += mod;
    }
    int q = 1ll * qpow(c, k) * qpow(b, k) % mod;
    int m = (n + 1) / k;
    if (q == 1) {
        int ans = 1ll * t1 * m % mod;
        ans = (1ll * ans * qpow(a, n)) % mod;
        cout << ans << '\n';
    } else {
        int ans = 1ll * t1 * (1 - qpow(q, m)) % mod * qpow(1 - q, phi - 1) % mod;
        if (ans < 0) ans += mod;
        ans = (1ll * ans * qpow(a, n)) % mod;
        cout << ans << '\n';
    }
    return 0;
}