시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 2 100.000%

문제

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

예제 출력 1

1

예제 입력 2

2

예제 출력 2

5

예제 입력 3

3

예제 출력 3

21