Заданы два целых числа $$$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}$$$.
Название |
---|