在UOJ管理员群里一共有$N$个管理员，为了容纳这些管理员，vfk准备了$N+1$个鸽笼。

为了节省空间，vfk把这些鸽笼堆了起来，共有$n$列，第$i$列放了$a_i$个鸽笼，满足 $\sum a_i=N+1$。

每当UR结束，管理员们就会按照编号从小到大的顺序回到鸽笼里，每个管理员回来的时候，会先等概率的在所有还有剩余的鸽笼的列中随机一个列，然后住到这列剩下的鸽笼里编号最小的一个中。

现在$N$个管理员都回笼了之后，还有一列会空出一个鸽笼。你能对于每一列，求出这一列有空鸽笼的概率吗？

输入格式

第一行一个整数$n$。

第二行$n$个正整数$a_i$。

输出格式

一行$n$个整数表示答案对$998244353$取模的结果。

样例一

input

3
1 1 1

output

332748118 332748118 332748118

explanation

都是$\frac{1}{3}$。

样例二

input

3
1 2 3

output

771790773 824938042 399759892

样例三

见样例数据下载。

限制与约定

对于所有数据，均满足 $1\le a_i\le 30,1\le n\le 30,\sum a_i\ge 1$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载