Alternating Sum
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定两个整数。 此外,您将获得一个序列 中的所有值都是整数 。 你知道这个序列的周期为,换句话说,对于每个,满足
再给你一个,求,由于答案可能很大,输出的结果即可。

输入描述:

第一行4个正整数,并且保证
第二行包含一个长度为的字符串,字符集只有,如果第 个字符是“+”,则 ,否则

输出描述:

输出一个整数表示答案。
示例1

输入

复制
2 2 3 3
+-+

输出

复制
7

说明

(\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
示例2

输入

复制
4 1 5 1
-

输出

复制
999999228

说明

(\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}

备注:

原题链接:https://codeforces.com/problemset/problem/963/A