# Codeforces 963 A. Alternating Sum （逆元）

## Description

You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It’s known that sequence is $k$-periodic and $k$ divides $n+1$. In other words, for each $k \leq i \leq n$ it’s satisfied that $s_{i} = s_{i – k}$.

Find out the non-negative remainder of division of $\sum \limits_{i=0}^{n} s_{i} a^{n – i} b^{i}$ by $10^{9} + 9$.

Note that the modulo is unusual!

## Input

The first line contains four integers $n, a, b$ and $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$.

The second line contains a sequence of length $k$ consisting of characters ‘+’ and ‘-‘.

If the $i$-th character (0-indexed) is ‘+’, then $s_{i} = 1$, otherwise $s_{i} = -1$.

Note that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property.

## Output

Output a single integer — value of given expression modulo $10^{9} + 9$.

## Examples input

2 2 3 3
+-+


## Examples output

7


## AC 代码

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 9;

LL a, b, n, k;
char str[maxn];
LL mult(LL a, LL n) {
LL ans = 1;
while (n) {
if (n & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}

void solve() {
LL ans = 0, res = 0;
LL inva = mult(a, mod - 2);
LL pw = mult(a, n);
LL lun = (n + 1) / k;
for (int i = 0; i < k; i++) {
res += (str[i] == '+' ? 1 : -1) * pw % mod;
res %= mod;
pw = pw * inva % mod * b % mod;
}
LL q = mult(inva, k) * mult(b, k) % mod;
if (q == 1) {
ans = res * lun % mod;
} else {
LL di = mult((q - 1 + mod) % mod, mod - 2);
LL de = (mult(q, lun) - 1 + mod) % mod;
ans = res * de % mod * di % mod;
}
ans = ((ans % mod) + mod) % mod;
cout << ans << endl;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
IO;
#endif // ONLINE_JUDGE

cin >> n >> a >> b >> k;
cin >> str;
solve();
return 0;
}