Spotkanie

Limit pamięci: 32 MB

Na drugim kongresie Bajtockiego Towarzystwa Informatyków (nazwanym dla odmiany po prostu spotkaniem) uczestnicy zasiedli przy okrągłym stole, wszyscy po zewnętrznej jego stronie. Jeden z uczestników postawił pytanie, na ile sposobów siedzący mogą się przywitać bez wstawania od stołu. Przywitanie takie polega na tym, że każdy uczestnik ściska dłoń co najwyżej jednego swojego sąsiada.

Ponieważ uczestnicy kongresu są informatykami teoretykami, poprosili Ciebie o napisanie programu, który policzy dla nich tę liczbę sposobów. Żeby nie operować dużymi liczbami wystarczy, jeżeli podasz im ostatnią cyfrę wyniku.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia liczbę uczestników kongresu,
• wyznaczy liczbę różnych sposobów przywitania się uczestników kongresu,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę uczestników kongresu.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znajdować się jedna cyfra, będąca ostatnią cyfrą szukanej liczby możliwych konfiguracji uścisków dłoni.

Przykład

4

7

Wszystkie możliwe konfiguracje uścisków dłoni.

Autor zadania: Jakub Radoszewski.