{"raw_statement":[{"iden":"statement","content":"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}$.\n\nFind out the **non-negative** remainder of division of $\\sum \\limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$ by $10^{9} + 9$.\n\n**Note that the modulo is unusual!**"},{"iden":"input","content":"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})$.\n\nThe second line contains a sequence of length $k$ consisting of characters '_+_' and '_\\-_'.\n\nIf the $i$\\-th character (0-indexed) is '_+_', then $s_{i} = 1$, otherwise $s_{i} = -1$.\n\nNote that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property."},{"iden":"output","content":"Output a single integer — value of given expression modulo $10^{9} + 9$."},{"iden":"examples","content":"Input\n\n2 2 3 3\n+-+\n\nOutput\n\n7\n\nInput\n\n4 1 5 1\n-\n\nOutput\n\n999999228"},{"iden":"note","content":"In the first example:\n\n$(\\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\n\nIn the second example:\n\n$(\\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}$."}],"translated_statement":[{"iden":"statement","content":"给你两个整数 $a$ 和 $b$。此外，给你一个序列 $s_0, s_1, dots.h, s_n$。序列 $s$ 中的所有值均为整数 $1$ 或 $-1$。已知该序列是 $k$-周期的，且 $k$ 整除 $n + 1$。换句话说，对于每个 $k lt.eq i lt.eq n$，都有 $s_i = s_(i -k)$。\n\n求表达式 $sum limits_(i = 0)^n s_i a^(n -i) b^i$ 除以 $10^9 + 9$ 的**非负余数**。\n\n*注意：模数不寻常！*\n\n第一行包含四个整数 $n, a, b$ 和 $k$ $(1 lt.eq n lt.eq 10^9, 1 lt.eq a, b lt.eq 10^9, 1 lt.eq k lt.eq 10^5)$。\n\n第二行包含一个长度为 $k$ 的字符序列，由字符 '_+_' 和 '_-_' 组成。\n\n如果第 $i$ 个字符（从 0 开始计数）是 '_+_'，则 $s_i = 1$；否则 $s_i = -1$。\n\n注意：仅给出了序列的前 $k$ 个元素，其余元素可通过周期性性质推导得出。\n\n输出一个整数——给定表达式对 $10^9 + 9$ 取模的值。"},{"iden":"input","content":"第一行包含四个整数 $n, a, b$ 和 $k$ $(1 lt.eq n lt.eq 10^9, 1 lt.eq a, b lt.eq 10^9, 1 lt.eq k lt.eq 10^5)$。第二行包含一个长度为 $k$ 的字符序列，由字符 '_+_' 和 '_-_' 组成。如果第 $i$ 个字符（从 0 开始计数）是 '_+_'，则 $s_i = 1$；否则 $s_i = -1$。注意：仅给出了序列的前 $k$ 个元素，其余元素可通过周期性性质推导得出。"},{"iden":"output","content":"输出一个整数——给定表达式对 $10^9 + 9$ 取模的值。"},{"iden":"examples","content":"输入\n2 2 3 3\n+-+\n输出\n7\n\n输入\n4 1 5 1\n-\n输出\n999999228"},{"iden":"note","content":"在第一个例子中：\n$(sum limits_(i = 0)^n s_i a^(n -i) b^i)$ = $2^23^0 -2^13^1 + 2^03^2$ = 7\n\n在第二个例子中：\n$(sum limits_(i = 0)^n s_i a^(n -i) b^i) = -1^45^0 -1^35^1 -1^25^2 -1^15^3 -1^05^4 = -781 equiv 999999228 pmod 10^(9) + 9$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ M = 10^9 + 9 $.  \nLet $ n, a, b, k \\in \\mathbb{Z} $ with constraints $ 1 \\le n \\le 10^9 $, $ 1 \\le a, b \\le 10^9 $, $ 1 \\le k \\le 10^5 $.  \nLet $ S = (s_0, s_1, \\dots, s_{k-1}) \\in \\{1, -1\\}^k $ be the base period of the sequence, where $ s_i $ is determined by the input character:  \n- $ s_i = 1 $ if the $ i $-th character is '+',  \n- $ s_i = -1 $ if the $ i $-th character is '-'.  \n\nThe full sequence $ (s_0, s_1, \\dots, s_n) $ is $ k $-periodic: for all $ i \\in \\{k, k+1, \\dots, n\\} $, $ s_i = s_{i \\bmod k} $.  \nIt is given that $ k \\mid (n+1) $.\n\n**Objective**  \nCompute:  \n$$\n\\sum_{i=0}^{n} s_i \\cdot a^{n-i} \\cdot b^i \\mod M\n$$\n\n**Constraints**  \n1. $ k \\mid (n+1) $  \n2. $ s_i = s_{i \\bmod k} $ for all $ i \\in \\{0, 1, \\dots, n\\} $  \n3. All arithmetic is performed modulo $ M = 10^9 + 9 $, with non-negative remainder.","simple_statement":null,"has_page_source":false}