CF963A.Alternating Sum

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!

给你两个整数 $a$ 和 $b$。此外，你被给定一个序列 $s_0, s_1, \dots, s_{n}$。序列 $s$ 中所有值均为整数 $1$ 或 $-1$。已知该序列是 $k$-周期性的，且 $k$ 整除 $n+1$。换言之，对每个满足 $k \leq i \leq n$ 的 $i$，均有 $s_{i} = s_{i - k}$。

求 $\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$ 除以 $10^{9} + 9$ 所得的非负余数。

注意：此处取模的模数是非同寻常的！

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.

第一行包含四个整数 $n, a, b$ 和 $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$。

第二行包含一个长度为 $k$ 的字符串，由字符 '+' 和 '-' 组成。

若第 $i$ 个字符（从 0 开始编号）为 '+'，则 $s_{i} = 1$；否则 $s_{i} = -1$。

注意：仅给出序列的前 $k$ 项，其余项可利用周期性性质得到。

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

输出一个整数——给定表达式的值对 $10^{9} + 9$ 取模的结果。

In the first example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i})$ = $2^{2} 3^{0} - 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7

In the second example:

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}) = -1^{4} 5^{0} - 1^{3} 5^{1} - 1^{2} 5^{2} - 1^{1} 5^{3} - 1^{0} 5^{4} = -781 \equiv 999999228 \pmod{10^{9} + 9}$.

在第一个例子中：

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i})$ = $2^{2} 3^{0} - 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7

在第二个例子中：

$(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}) = -1^{4} 5^{0} - 1^{3} 5^{1} - 1^{2} 5^{2} - 1^{1} 5^{3} - 1^{0} 5^{4} = -781 \equiv 999999228 \pmod{10^{9} + 9}$。