2395: Mushroom Gnomes
Description
Once upon a time in the thicket of the mushroom forest lived mushroom gnomes. They were famous among their neighbors for their magic mushrooms. Their magic nature made it possible that between every two neighboring mushrooms every minute grew another mushroom with the weight equal to the sum of weights of two neighboring ones.
The mushroom gnomes loved it when everything was in order, that's why they always planted the mushrooms in one line in the order of their weights' increasing. Well... The gnomes planted the mushrooms and went to eat. After x minutes they returned and saw that new mushrooms had grown up, so that the increasing order had been violated. The gnomes replanted all the mushrooms in the correct order, that is, they sorted the mushrooms in the order of the weights' increasing. And went to eat again (those gnomes were quite big eaters). What total weights modulo p will the mushrooms have in another y minutes?
The first line contains four integers n, x, y, p (1≤n≤106,0≤x,y≤1018,x+y>0,2≤p≤109) which represent the number of mushrooms, the number of minutes after the first replanting, the number of minutes after the second replanting and the module. The next line contains n integers ai which represent the mushrooms' weight in the non-decreasing order (0≤ai≤109).
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).
The answer should contain a single number which is the total weights of the mushrooms modulo p in the end after x+y minutes.
2 1 0 657276545
1 2
6
2 1 1 888450282
1 2
14
4 5 0 10000
1 2 3 4
1825