A. Знакопеременная сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы два целых числа $$$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$$$ из знаков '+' и '-'. Если символ c номером $$$i$$$ (нумерация с 0) — это +, то $$$s_{i} = 1$$$, иначе $$$s_{i} = -1$$$.

Обратите внимание, заданы только первые $$$k$$$ членов последовательности, остальные можно получить, используя свойство периодичности.

Выходные данные

Выведите одно целое число — значение данного выражения по модулю $$$10^{9} + 9$$$.

Примеры
Входные данные
2 2 3 3
+-+
Выходные данные
7
Входные данные
4 1 5 1
-
Выходные данные
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}$$$.