牛牛的粉丝
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛牛的粉丝如此之多，以至于为了举办粉丝见面会不得不在一个有 个点的环上举行，环的编号为 。

对于环上每个点  定义它的顺时针方向的下一个点的是 。

牛牛打算对粉丝的位置进行 轮调整，但是由于场地过于巨大导致粉丝们听不清牛牛的指令，在每一轮 每一个粉丝都会独立地以 p_1 的概率向顺时针方向走一步，以 p_2 的概率向逆时针方向走一步，当然也有 p_3 的概率被牛牛帅傻了，站在原地不动。

由于粉丝过多，移动的时候就会很乱 所以牛牛只想知道结果： 轮移动结束后 每个点上人数的期望是多少？答案对  取模。

输入描述:

第一行二个正整数 。

第二行三个正整数 ,设 ,则 

接下来一行  个整数，第  个整数 x_i 表示初始时站在 位置上的粉丝的个数。 

输出描述:

输出  个整数 表示每个位置的期望人数。
示例1

输入

复制 
3 1
1 1 1
1 0 0

输出

复制 
332748118 332748118 332748118

说明

牛牛的粉丝有 \frac{1}{3} 的概率顺时针，逆时针和不动。那么一轮后在每一个位置上的概率都是 \frac{1}{3} 所以每一个位置上人数的期望就是 \frac{1}{3}。
示例2

输入

复制 
4 2
1 1 2
1 1 0 0

输出

复制 
374341633 374341633 623902721 623902721

备注: