← 返回题目列表

Codeforces · 963/A

A. 交替求和

中文机器翻译题面 查看原题

给定两个整数 $$$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}$$$。