Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Mushroom Gnomes

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOnce 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* ≤ 10^{6}, 0 ≤ *x*, *y* ≤ 10^{18}, *x* + *y* > 0, 2 ≤ *p* ≤ 10^{9}) 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 *a*_{i} which represent the mushrooms' weight in the non-decreasing order (0 ≤ *a*_{i} ≤ 10^{9}).

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/27/2021 16:09:30 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|