Futbolkalar#4814
Bugünkü idman məşğələsində LKSH tələbəsi sıraya düzülüb. Təbii ki, tələbələr fərqli rəngli köynəklər geyinirlər. Hörmətli bədən tərbiyəsi müəllimimiz Boris Andriyeviç müşahidə etdi ki, bəzi tələbələrə oturmağı tapşırmaq olar və beləliklə, ayaqda qalan tələbələr üçün köynək rənglərinin ardıcıllığı (soldan sağa baxdıqda) sağdan sola baxdıqda ilə eyni olur — yəni, bu ardıcıllıq palindromdur.
Məsələn, əgər Maşa yaşıl köynəkdə, Paşa sarı köynəkdə, Serioja qırmızı köynəkdə, Vanya isə yaşıl köynəkdə gəlibsə, Boris Paşaya oturmağı tapşırarsa, nəticədə "yaşıl, qırmızı, yaşıl" ardıcıllığı alınar ki, bu da palindromdur. Eynilə, Seriojaya oturmağı tapşırarsa ("yaşıl, sarı, yaşıl" alınar), həm Paşa, həm Serioja oturarsa və ya yalnız bir uşağın ayaqda qalmasına imkan versə də olar. Ümumilikdə, rəng ardıcıllığını palindrom etmək üçün fərqli yol var.
Boris Andriyeviçə kömək edin: bəzi LKSH tələbələrinə oturmağı tapşırmaqla əldə olunan köynək rənglərinin ardıcıllığını palindroma çevirməyin neçə yolu olduğunu müəyyənləşdirin. Bu say çox böyük ola biləcəyindən, onu 10^9-a bölünmədən qalıq şəklində çıxış verin.
Birinci sətirdə tam ədədi verilir (1 \leq N \leq 2000) — sıradakı LKSH tələbələrinin sayı. İkinci sətirdə ədəd var, hər biri tələbənin köynəyinin rəngini göstərir, -dən 10^9-a qədər. Fərqli rənglər fərqli ədədlərlə, eyni rənglər eyni ədədlərlə təqdim olunur.
Bir tam ədəd çıxış verin — tələb olunan yolların sayını 10^9-a bölünmədən qalıq şəklində.
Nümunə 1