Заданы два целых числа \(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\).
Примечание
В первом тестовом примере:
\((\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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 3 3
+-+
|
7
|
|
2
|
4 1 5 1
-
|
999999228
|