Alternating Sum

두 정수 a와 b가 주어진다. 또한 수열 $s_0$, $s_1$, ..., $s_{n}$가 주어진다. s의 모든 값은 정수 1 또는 -1이다. 이 수열은 k-주기적이며, k가 n+1을 나눈다는 것이 알려져 있다. 다시 말해, 각 k ≤ i ≤ n에 대해 $s_{i}$ = $s_{i - k}$가 성립한다.

∑ _{i=0}^{n} $s_{i}$ $a^{n - i}$ $b^{i}$을 $10^{9}$ + 9로 나눈 음이 아닌 나머지를 구한다.

나누는 법이 특이하다는 점에 유의한다!

첫째 줄에 네 정수 n, a, b, k가 주어진다 (1 ≤ n ≤ $10^{9}$, 1 ≤ a, b ≤ $10^{9}$, 1 ≤ k ≤ $10^{5}$).

둘째 줄에 문자 '+'와 '-'로 구성된 길이 k의 수열이 주어진다.

인덱스를 0부터 셀 때 i-th 문자가 '+'이면 $s_{i}$ = 1이고, 그렇지 않으면 $s_{i}$ = -1이다.

수열의 처음 k개 원소만 주어지며, 나머지는 주기성으로 구할 수 있다는 점에 유의한다.

주어진 식의 값을 $10^{9}$ + 9로 나눈 나머지를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 다음과 같다.

(∑ _{i=0}^{n} $s_{i}$ $a^{n - i}$ $b^{i}$) = $2^{2}$ $3^{0}$ - $2^{1}$ $3^{1}$ + $2^{0}$ $3^{2}$ = 7

두 번째 예제에서는 다음과 같다.

(∑ _{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 ≡ 999999228 $\pmod{10^{9} + 9}$.