有 $n$ 个鲲，标号从 $1$ 到 $n$，每个鲲一开始的体重都是 $1$。鲲非常能吃，所以每 $1$ 秒第 $i$ 个鲲的体重会变成上一秒的 $a_i$ 倍。具体来说，在第 $k$ 秒的时候，第 $i$ 个鲲的体重是 $a_i^k$。
鲲是可以合成的，合成的方法是选取一组 $x_i$ 使得 $\sum_{i=1}^n x_i=1$，那么合成出来的鲲在第 $k$ 秒的体重就是 $\sum_{i=1}^n x_i a_i^k$。需要注意的是，因为鲲是上古神兽，所以 $x_i$ 不一定要在 $[0,1]$ 内。
现在你想要使得合成出来的结果在前 $n-1$ 秒内等价于一个增长系数为 $b$ 的一个鲲，也就是在第 $k$ 秒合成出来的鲲的重量是 $b^k$ 。现在你想要知道合成系数 $x_i$ 的取值，并对 $1811939329$ 取模。
数据保证有解且解唯一。
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数，表示 $a_i$ 。
第三行一个整数 $b$ 。
输出格式
一行 $n$ 个整数，第 $i$ 个整数表示 $x_i$ 对 $1811939329$ 取模的结果。
样例
input
2 1 2 3
output
1811939328 2
限制与约定
Subtask1（20分）：$1\leq n \leq 100$；
Subtask2（30分）：$1 \leq n \leq 1000$；
Subtask3（50分）：$1 \leq n \leq 100000$。
时间限制：3s
空间限制：512MB
