CF60E Mushroom Gnomes

很久以前，在蘑菇森林的灌木丛中生活着蘑菇地精。它们以神奇的蘑菇而在邻居中闻名。它们的神奇特性使得它们每分钟可以在相邻的两个蘑菇之间长出另一个蘑菇，而该蘑菇的重量等于两个相邻蘑菇的重量之和。 蘑菇地精喜欢一切都井井有条的，这就是为什么它们总是按照重量递增的顺序将蘑菇种成一行。 地精们种下蘑菇后就去吃饭了。 $x$ 分钟后，他们返回，发现新的蘑菇长大了，因此打破了递增的顺序。 地精们按照正确的顺序重新种植了所有蘑菇，也就是说，他们按照重量递增的顺序重新对蘑菇进行了排序。然后又去吃饭了（地精们是食量很大的）。 再过 $y$ 分钟，蘑菇总重量对 $p$ 取模的值是多少？

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

答案应包含一个数字，即蘑菇在 $x+y$ 分钟后的总重量对 $p$ 取模的值。