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의 수열이 주어진다.

i-th 문자(0부터 인덱싱)가 '+'이면 $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}$.