ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4971: Mushroom Gnomes

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

E. Mushroom Gnomes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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?
Input
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).
Output
The answer should contain a single number which is the total weights of the mushrooms modulo p in the end after x+y minutes.
Examples
Input 
2 1 0 657276545
1 2
Output 
6
Input 
2 1 1 888450282
1 2
Output 
14
Input 
4 5 0 10000
1 2 3 4
Output 
1825

输入样例 复制

输出样例 复制

分类标签