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 nonnegative 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 (0indexed) 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$$$.
2 2 3 3
++
7
4 1 5 1

999999228
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}$$$.
Name 
