题目描述

给定两个整数 $\ a$ 和 $\ b$。 此外，您将获得一个序列 $\ s_0,s_1,...,s_n$。 $\ s$ 中的所有值都是整数  $\ 1$ 或 $\ -1$。 你知道这个序列的周期为 $\ k$，换句话说，对于每个 $\ k≤i≤n$，满足 $\ s_i=s_{i−k}$。
再给你一个 $\ n$，求$\sum_{i=0}^n s_ia^{n-i}b^i$，由于答案可能很大，输出 $\ mod\ 10^9+9$的结果即可。

输入格式

第一行4个正整数 $\ n,a,b,k (1≤n,a,b≤10^9,1≤k≤min(n+1,10^5))$，并且保证 $\ (n+1)\%k=0$。

第二行包含一个长度为 $\ k$的字符串 $\ s$，字符集只有 $\ +$和 $\ -$，如果第 $\ i$ 个字符是“+”，则  $\ s_i=1$，否则 $\ s_i=-1$， $\ 0≤i＜k$。

输出格式

输出一个整数表示答案。

样例

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$

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}$