题目描述

小蓝最近非常热衷于斗蛐蛐。她有 $n$ 只不同的蛐蛐，每只蛐蛐的战斗力都可以用一个数 $a_i$ 表示，含义是当第 $i$ 只蛐蛐攻击别的蛐蛐时有 $a_i$ 的概率打倒对方，有 $1 - a_i$ 的概率无事发生。

小蓝将 $n$ 只蛐蛐按编号由 $1$ 到 $n$ 顺时针的顺序排成一圈，然后从 $1$ 号蛐蛐开始发生以下的过程直到只剩下 $1$ 只蛐蛐：

1. 这只蛐蛐以各 $1/2$ 的概率选定顺时针或逆时针方向。
2. 这只蛐蛐攻击这个方向上第一只未被打倒的蛐蛐。
3. 无论这次攻击是否打倒了蛐蛐，顺时针方向的下一只蛐蛐开始行动。

现在小蓝希望知道，最后剩下的蛐蛐是 $i$ 号蛐蛐的概率是多少。为了防止精度误差，她希望你给出这个值在模素数 $m$ 下的结果。

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔。

第二行包含 $n$ 个正整数，其中第 $i$ 个正整数表示第 $i$ 只蛐蛐在模 $m$ 下的战斗力 $a_i$。

输出格式

输出一行包含 $n$ 整数，相邻整数之间使用一个空格分隔，其中第 $i$ 个整数表示最后一只蛐蛐是 $i$ 号蛐蛐的概率在模 $m$ 下的表示。

2 1000000007
500000004 500000004

666666672 333333336

提示

样例说明

一共两只蛐蛐，蛐蛐的战斗力都是 $1/2$，$1$ 号蛐蛐攻击 $2$ 号蛐蛐若成功，则 $1$ 号蛐蛐获胜，若失败则相当于双方位置交换，所以最终 $1$ 号蛐蛐获胜概率 $p$ 满足 $p = 1/2 + 1/2(1 - p)$ 解得 $p = 2/3$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$n \leq 8$，$a_i = (m + 1)/2$，即 $a_i$ 在模 $m$ 意义下为 $\frac{1}{2}$；
• 对于 $50\%$ 的评测用例，$n \leq 8$；
• 对于所有评测用例，$2 \leq a_i < m \leq 10^9 + 7$，$2 \leq n \leq 15$，$m$ 必定为一个大于 $2$ 的素数。