Archiwum zadań programistycznych WWSI

Podczas przygotowywania statystyk dotyczących ostatnich Mistrzostw WWSI w Programowaniu zauważyliśmy pewną bardzo ciekawą zależność. Okazało się, że liczba zgłoszeń nadesłanych w ciągu każdej godziny późniejszej niż k-ta jest równa sumie zgłoszeń nadesłanych w ciągu k poprzednich godzin. Od tamtej pory zastanawiamy się ile zgłoszeń zostało przesłanych w n-tej godzinie zawodów. Pomóż nam rozwiązać ten problem! Ponieważ domyślamy się, że zgłoszeń mogło być całkiem sporo zdecydowaliśmy, że wystarczy nam reszta z dzielenia ich liczby przez m.

Wejście

W pierwszej linii wejścia znajdują się trzy liczby całkowite k, n oraz m (1 ≤ k ≤ 100, 1 ≤ n ≤ 10⁹, 2 ≤ m ≤ 10⁹) opisane powyżej. W drugiej linii znajduje się k liczb z zakresu od 1 do 10⁶. Liczba i-ta w kolejności określa ile zgłoszeń napłynęło w i-tej godzinie zawodów.

Wyjście

Na wyjściu należy wypisać resztę z dzielenia liczby zgłoszeń nadesłanych w n-tej godzinie przez m.

Przykład

Wejście

5 100 1000000
1 2 2 3 4

Wyjście

304003