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