CF60E.Mushroom Gnomes

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?

很久以前，在蘑菇森林的密林中住着一群蘑菇小矮人。他们在邻居中以魔法蘑菇而闻名。这种魔法特性使得每过一分钟，任意两株相邻的蘑菇之间都会生长出一株新蘑菇，其重量等于这两株相邻蘑菇重量之和。

蘑菇小矮人喜欢一切井然有序，因此他们总是将蘑菇按重量递增的顺序种成一条直线。嗯……小矮人们种好蘑菇后便去吃饭了。过了 $x$ 分钟后，他们返回发现已长出了新的蘑菇，导致原有的递增顺序被破坏。于是小矮人将所有蘑菇重新种植，即按重量递增顺序进行排序，然后再次去吃饭（这些小矮人的食量可真不小）。那么，再过 $y$ 分钟后，所有蘑菇的总重量对 $p$ 取模的结果是多少？

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 a__i which represent the mushrooms' weight in the non-decreasing order (0 ≤ a__i ≤ 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).

第一行包含四个整数 $n$、$x$、$y$、$p$（$1 ≤ n ≤ 10^6$，$0 ≤ x, y ≤ 10^{18}$，$x + y > 0$，$2 ≤ p ≤ 10^9$），分别表示蘑菇的数量、第一次重新种植后的分钟数、第二次重新种植后的分钟数以及模数。
下一行包含 $n$ 个整数 $a_i$，表示蘑菇的重量，按非递减顺序排列（$0 ≤ a_i ≤ 10^9$）。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 格式说明符。推荐使用 cin（也可使用 %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.

答案应为最终经过 $x + y$ 分钟后所有蘑菇的总重量对 $p$ 取模所得的单个数字。