Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Zgłaszanie Wszystkie zgłoszenia Najlepsze PDF Lista

AL_26_06 - Alfabet

Alfabet

Dany jest alfabet złożony z n różnych liter. Ciąg liter z tego alfabetu nazwiemy słowem, jeśli między dwiema takimi samymi literami nie ma innej pary takich samych liter. Ile jest słów nad tym alfabetem o maksymalnej długości?


Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 104) oznaczająca liczbę przypadków testowych. Dla każdego przypadku, w osobnym wierszu, znajduje się liczba całkowita n (1 ≤ n ≤ 106) oznaczająca długość alfabetu.

Wyjście
Dla każdego przypadku testowego należy wypisać resztę z dzielenia przez 109+9 liczby będącej odpowiedzią na zadane pytanie.

Przykład

Wejście
2
2
3

Wyjście
4
24

Dla alfabetu złożonego z dwóch liter otrzymujemy cztery słowa o maksymalnej długości: aaabbb, aababb, bbbaaa, bbabaa

Submit solution!
Dodane przez:Mariusz Śliwiński
Data dodania:2015-12-01
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.