시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 155 | 96 | 77 | 61.600% |
Jak wiadomo, do wymiany żarówki często wystarcza jedna osoba. Jeśli sufit jest za wysoko, potrzebujemy już pięciu ludzi: jeden stoi na stole trzymając żarówkę a reszta kręci stołem.
Jeśli sufit jest jeszcze wyżej, można pójść o krok dalej: jedna osoba trzyma żarówkę, cztery osoby trzymają stół, a dodatkowo każda z tych czterech osób także stoi na stole, utrzymywanym przez kolejne cztery osoby. Razem daje to 1 + 4 + 16 = 21 osób. Metodę tę można oczywiście rozszerzać w zależności od wysokości sufitu.
Oblicz, ile osób potrzebnych jest do zbudowania konstrukcji o zadanej wysokości. Ponieważ wynik może być bardzo duży, wystarczy, że podasz jego resztę z dzielenia przez 500000009.
Na wejściu znajduje się dokładnie jedna liczba całkowita A (1<=A<=1000000), oznaczająca ilość poziomów konstrukcji, jaką musimy osiągnąć.
Minimalna liczba osób potrzebna do wymiany żarówki, podana modulo 500000009 (zamiast liczby, należy wypisać jej resztę z dzielenia przez 500000009).
1
1
2
5
3
21
Contest > Spot > FallSpot 2009 1-1번