A11709 | 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!

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 a single integer — value of given expression modulo $10^{9} + 9$ .