Kółko informatyczne

Poeta

Grupa starsza

Limit pamięci: 8MB.
Pewien bajtocki poeta chce napisać wiersz. Należy jednak do ubogiego kręgu kulturowego i dostępne jest mu tylko 0≤T≤2000 toposów i jedynie 0≤A≤2000 archetypów. Obmyślając kolejne fragmenty poeta może:

• zapisać wers używając jednego z nie użytych jeszcze toposów,
• zapisać wers używając jednego z nie użytych archetypów,
• zapisać wers wyrażający n-elementową (n>0) antropomorfizację, zamieniając tym samym pierwsze n (alfabetycznie) nie użytych toposów w nowe archetypy,
• albo zakończyć utwór (może być pusty).

Poeta zastanawia się, jakie jest prawdopodobieństwo, że napisze najlepszy możliwy poemat. W tym celu chciałby dowiedzieć się, ile różnych utworów może napisać powyższą procedurą. Każdy wers używający danego toposu lub archetypu wygląda tak samo. Każda n-elementowa antropomorfizacja wygląda tak samo (niezależnie od tego co zamieni). Poznał też ostatnio Chińskie Twierdzenie o Resztach i twierdzi, że wystarczy mu, jeśli podasz odpowiedź modulo 1<M<2^30.

Wejście

W jedynej linii wejścia dane są trzy liczby: T,A,M.

Wyjście

W jedynej linii wyjścia wypisz liczbę różnych wierszy możliwych do uzyskania, modulo M.

Przykład

2 0 1000

26

[Zgłoś rozwiązanie]   [Moje zgłoszenia]