Как-то раз, проснувшись с утра и обнаружив, что у него украли дом, Рудольф понял, что ему необходимо защитить свой участок от подобных вторжений. Он решил построить забор и для этого закупил в строительном магазине доски. Когда он вернулся из магазина и осмотрел свою покупку, он понял, что не все доски имеют одинаковую длину. Тогда Рудольф решил выйти из ситуации самым очевидным образом, а именно — построить симметричный забор.
Забор из n досок Рудольф считает симметричным, если доски в позициях i и (n - i + 1), где 
, имеют равные высоты.
Ко всему прочему Рудольф хочет, чтобы его забор имел максимальную длину. Однако, он внезапно осознал, что способов построить такой забор может быть очень много, и попросил вас помочь ему подсчитать их количество. Два способа построения забора считаются различными, если высоты досок отличаются хотя бы в одной позиции.
Помогите Рудольфу узнать ответ на его вопрос.
Первая строка содержит целое число n (1 ≤ n ≤ 105) — количество досок у Рудольфа.
Вторая строка содержит n целых чисел hi (1 ≤ hi ≤ 1018) — высоту каждой из досок.
Выведите одно целое число — количество различных способов составить симметричный забор максимальной длины из имеющихся у Рудольфа досок. Так как это количество может оказаться достаточно большим, выведите остаток от его деления на (109 + 9).
5
2 1 2 2 1
2
6
1 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).
