E. Грибные гномы
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Жили-были где-то в чаще грибного леса грибные гномы. Они были знамениты на всю округу своими волшебными грибами. Грибы были волшебны тем, что между каждыми двумя соседними грибами каждую минуту вырастал ещё один, с массой, равной сумме масс соседних. Грибные гномы любили порядок, поэтому они всегда сажали грибы в одну линию по увеличению их массы. Так вот... Гномы посадили грибы и ушли есть. Через x минут они вернулись и увидели, что выросли новые грибы, а поэтому возрастающий порядок был нарушен. Гномы пересадили все грибы в правильном порядке, то есть отсортировали по увеличению массы. И опять ушли есть (это были очень прожорливые гномы). Какая суммарная масс по модулю p будет у грибов ещё через y минут?

Входные данные

В первой строке содержится четыре целых числа n, x, y, p (1 ≤ n ≤ 106, 0 ≤ x, y ≤ 1018, x + y > 0, 2 ≤ p ≤ 109) — количество грибов, число минут после первой посадки, число минут после второй посадки и модуль. В следующей строке содержится n целых чисел ai — веса грибов в неубывающем порядке (0 ≤ ai ≤ 109).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).

Выходные данные

В ответе должно быть одно число — суммарная масса грибов по модулю p в конце, после x + y минут.

Примеры
Входные данные
2 1 0 657276545
1 2
Выходные данные
6
Входные данные
2 1 1 888450282
1 2
Выходные данные
14
Входные данные
4 5 0 10000
1 2 3 4
Выходные данные
1825