Preparando MOJI
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$$$.
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}$$$.
Informação
Provedor Codeforces
Código CF963A
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:33:39
Relacionados