从前,蘑菇森林的灌木丛里住着蘑菇侏儒。他们因神奇蘑菇而在邻居中闻名。它们的神奇性质使得每两个相邻蘑菇之间每分钟就会长出另一个蘑菇,其重量等于两个相邻蘑菇的重量总和。
蘑菇侏儒喜欢一切都井然有序的样子,这就是为什么他们总是按照蘑菇重量增加的顺序将蘑菇种植成一排。嗯……侏儒们种下了蘑菇就去吃了。 x分钟后,他们返回,发现新蘑菇已经长出来,因此递增顺序被破坏了。侏儒按照正确的顺序重新种植了所有蘑菇,也就是说,他们按照重量增加的顺序对蘑菇进行了排序。然后又去吃饭了(那些侏儒的食量相当大)。再过 y 分钟,蘑菇的总重量模 p 是多少?
输入
第一行包含四个整数n、x、y、p(1 ≤ n ≤ 106, 0 ≤ x, y ≤ 1018, x + y > 0, 2 ≤ p ≤ 109),分别代表蘑菇的数量、第一次重新种植后的分钟数、第二次重新种植后的分钟数和模块。下一行包含 n 个整数 ai,它们按非递减顺序表示蘑菇的重量 (0 ≤ ai ≤ 109)。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin (也可以使用 %I64d)。
输出
答案应包含一个数字,即 x + y 分钟后最后蘑菇的总重量以 p 为模。
示例
输入 #1
2 1 0 657276545 1 2
输出 #1
6
输入 #2
2 1 1 888450282 1 2
输出 #2
14
输入 #3
4 5 0 10000 1 2 3 4
输出 #3
1825