CF963A Alternating Sum

给定两个整数 $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$ 的非负余数。 注意，这里的模数是 $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$ 取模后的值。

在第一个样例中： $\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}$。 由 ChatGPT 4.1 翻译