Жили-были где-то в чаще грибного леса грибные гномы. Они были знамениты на всю округу своими волшебными грибами. Грибы были волшебны тем, что между каждыми двумя соседними грибами каждую минуту вырастал ещё один, с массой, равной сумме масс соседних. Грибные гномы любили порядок, поэтому они всегда сажали грибы в одну линию по увеличению их массы. Так вот... Гномы посадили грибы и ушли есть. Через x минут они вернулись и увидели, что выросли новые грибы, а поэтому возрастающий порядок был нарушен. Гномы пересадили все грибы в правильном порядке, то есть отсортировали по увеличению массы. И опять ушли есть (это были очень прожорливые гномы). Какая суммарная масс по модулю p будет у грибов ещё через y минут?
Выходные данные
В ответе должно быть одно число — суммарная масса грибов по модулю p в конце, после x + y минут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 0 657276545
1 2
|
6
|
|
2
|
2 1 1 888450282
1 2
|
14
|
|
3
|
4 5 0 10000
1 2 3 4
|
1825
|