eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Узагальнені бурундуки Фібоначчі

Узагальнені бурундуки Фібоначчі

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Як відомо, бурундуки живуть a років. Бурундуки - істоти щедрі на кохання, тому кожного року серед них народжуються нові. А саме, якщо у рік y у якомусь місці усього було b бурундуків, то у рік y + 1 народиться ще b.

Нещодавно Вася пограбував зоомагазин. Так як Вася достатньо добре разбирається у бурундуках, уважно вивчивши конкретну тварину, він може визначити її вік. Саме цим грабіжник і зайнявся у перший же день знайомства зі своєю здобиччю. На його подив, серед звірів виявилось рівно n[1] бурундуків, яким усього 1 рік, рівно n[2] бурундуків віком у 2 роки, і так далі.

Тепер Вася зацікавився, скільки ж бурундуків у нього буде через k років. А так як у нього з шкільних років велика неприязнь до великих чисел, то йому набагато більше хочеться побачити це число по модулю m.

Вхідні дані

У першому рядку знаходиться число a (1a5) - термін життя бурундуків. У наступному рядку знаходяться числа n[1], n[2], ..., n[a] (0n[i]100) - кількості бурундуків віком у 1, 2, ..., a років відповідно. В останньому рядку знаходиться два числа k та m (0k10^9, 1 < m10^9) - проміжок часу, який нас цікавить, та модуль, по якому потрібно вивести кількість бурундуків.

Вихідні дані

Виведіть єдине число - кількість бурундуків через k років за модулем m.

Приклад

Вхідні дані #1
2
1 0
5 10000
Вихідні дані #1
13
Автор М.Дворкін, В.Фондаратов