Обобщенные бурундуки Фибоначчи
Как известно, бурундуки живут a лет. Бурундуки - существа любвеобильные, поэтому каждый год среди них рождаются новые. А именно, если в год y в каком-либо месте всего было b бурундуков, то в год y + 1 родится еще b.
Недавно Вася ограбил зоомагазин. Так как Вася достаточно хорошо разбирается в бурундуках, внимательно изучив конкретное животное, он может определить его возраст. Именно этим грабитель и занялся в первый же день знакомства со своей добычей. К его удивлению, среди зверей оказалось ровно n[1] бурундуков, которым всего 1 год, ровно n[2] бурундуков возрастом в 2 года, и так далее.
Теперь Вася заинтересовался, сколько же бурундуков у него будет через k лет. А так как у него со школьных лет большая нелюбовь к большим числам, ему намного больше хочется увидеть это число по модулю m.
Входные данные
В первой строке находится число a (1 ≤ a ≤ 5) - срок жизни бурундуков. В следующнй строке находятся числа n[1], n[2], ..., n[a] (0 ≤ n[i] ≤ 100) - количества бурундуков возрастом в 1, 2, ..., a лет соответственно. В последней строке находится два числа k и m (0 ≤ k ≤ 10^9, 1 < m ≤ 10^9) - интересуемый промежуток времени, и модуль, по которому требуется вывести количество бурундуков.
Выходные данные
Выведите единственное число - количество бурундуков через k лет по модулю m.