给定两个整数 $$$a$$$ 和 $$$b$$$。此外,还给你一个序列 $$$s_0, s_1, \dots, s_{n}$$$。 $$$s$$$ 中的所有值都是整数 $$$1$$$ 或 $$$-1$$$。众所周知,序列是 $$$k$$$ 周期性的,并且 $$$k$$$ 整除 $$$n+1$$$。换句话说,对于每个$$$k \leq i \leq n$$$,满足$$$s_{i} = s_{i - k}$$$。
找出 $$$\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$$$ 除以 $$$10^{9} + 9$$$ 的非负余数。
请注意,模数是不寻常的!
输入
第一行包含四个整数 $$$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$$$ 成员,其余成员可以使用周期性属性获得。
输出
输出单个整数 - 给定表达式模 $$$10^{9} + 9$$$ 的值。
示例
输入 #1
2 2 3 3 +-+
输出 #1
7
输入 #2
4 1 5 1 -
输出 #2
999999228
注意
在第一个示例中:
$$$(\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}$$$。