Как-то раз, проснувшись с утра и обнаружив, что у него украли дом, Рудольф понял, что ему необходимо защитить свой участок от подобных вторжений. Он решил построить забор и для этого закупил в строительном магазине доски. Когда он вернулся из магазина и осмотрел свою покупку, он понял, что не все доски имеют одинаковую длину. Тогда Рудольф решил выйти из ситуации самым очевидным образом, а именно — построить симметричный забор.
Забор из n досок Рудольф считает симметричным, если доски в позициях i и (n - i + 1), где , имеют равные высоты.
Ко всему прочему Рудольф хочет, чтобы его забор имел максимальную длину. Однако, он внезапно осознал, что способов построить такой забор может быть очень много, и попросил вас помочь ему подсчитать их количество. Два способа построения забора считаются различными, если высоты досок отличаются хотя бы в одной позиции.
Помогите Рудольфу узнать ответ на его вопрос.
Первая строка содержит целое число n (1 ≤ n ≤ 105) — количество досок у Рудольфа.
Вторая строка содержит n целых чисел hi (1 ≤ hi ≤ 1018) — высоту каждой из досок.
Выведите одно целое число — количество различных способов составить симметричный забор максимальной длины из имеющихся у Рудольфа досок. Так как это количество может оказаться достаточно большим, выведите остаток от его деления на (109 + 9).
В первом примере существуют два способа составления симметричного забора из всех имеющихся досок: (1, 2, 2, 2, 1) и (2, 1, 2, 1, 2).
Во втором примере для получения максимально длинного забора мы можем задействовать только 5 досок и составить следующие симметричные заборы: (1, 2, 1, 2, 1), (1, 2, 3, 2, 1), (2, 1, 1, 1, 2), (2, 1, 3, 1, 2).
## Входные Данные
Первая строка содержит целое число n (1 ≤ n ≤ 105) — количество досок у Рудольфа.Вторая строка содержит n целых чисел hi (1 ≤ hi ≤ 1018) — высоту каждой из досок.
## Выходные Данные
Выведите одно целое число — количество различных способов составить симметричный забор максимальной длины из имеющихся у Рудольфа досок. Так как это количество может оказаться достаточно большим, выведите остаток от его деления на (109 + 9).
## Примеры
Входные данные52 1 2 2 1Выходные данные2Входные данные61 3 2 2 1 1Выходные данные4
## Примечание
В первом примере существуют два способа составления симметричного забора из всех имеющихся досок: (1, 2, 2, 2, 1) и (2, 1, 2, 1, 2).Во втором примере для получения максимально длинного забора мы можем задействовать только 5 досок и составить следующие симметричные заборы: (1, 2, 1, 2, 1), (1, 2, 3, 2, 1), (2, 1, 1, 1, 2), (2, 1, 3, 1, 2).
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of boards.
Let $ H = (h_1, h_2, \dots, h_n) $ be a sequence of integers representing the heights of the boards.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq h_i \leq 10^{18} $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the number of distinct symmetric fences of **maximum possible length** that can be constructed using a subset of the boards, where a fence of length $ \ell $ is symmetric if for all $ i \in \{1, \dots, \lfloor \ell/2 \rfloor\} $, the height at position $ i $ equals the height at position $ \ell - i + 1 $.
Two fences are distinct if their height sequences differ in at least one position.
Output the count modulo $ 10^9 + 9 $.
**Key Insight**
The maximum length $ \ell $ of a symmetric fence is determined by the maximum number of boards that can be paired symmetrically (with possibly one unpaired center board). For each distinct height $ v $, let $ c_v $ be its frequency in $ H $.
To maximize $ \ell $:
- For each $ v $, we can use at most $ \left\lfloor \frac{c_v}{2} \right\rfloor $ pairs.
- Let $ P = \sum_v \left\lfloor \frac{c_v}{2} \right\rfloor $ be the total number of usable pairs.
- Then maximum fence length is $ \ell = 2P + r $, where $ r = 1 $ if there exists at least one $ v $ with $ c_v $ odd, else $ r = 0 $.
The number of distinct symmetric fences of length $ \ell $ is:
- If $ r = 1 $: choose **one** center height from all $ v $ with odd $ c_v $, and assign the $ P $ pairs to the $ P $ symmetric positions.
- The number of ways to assign the pairs is the multinomial coefficient:
$$
\frac{P!}{\prod_v \left( \left\lfloor \frac{c_v}{2} \right\rfloor ! \right)}
$$
- Multiply by the number of choices for the center: $ \#\{ v \mid c_v \text{ is odd} \} $.
If $ r = 0 $: no center, so only the multinomial coefficient.
Thus, the answer is:
$$
\left( \#\{ v \mid c_v \text{ odd} \} \right)^r \cdot \frac{P!}{\prod_v \left( \left\lfloor \frac{c_v}{2} \right\rfloor ! \right)} \mod (10^9 + 9)
$$