在荷马的学校里,有$$$n$$$ 的学生热爱俱乐部。
最初,有 $$$m$$$ 个俱乐部,并且每个 $$$n$$$ 学生都属于一个俱乐部。换句话说,第 $$$i$$$ 俱乐部中有 $$$a_i$$$ 学生,$$$1 \leq i \leq m$$$ 和 $$$a_1+a_2+\dots+a_m = n$$$。
$$$n$$$ 学生非常不友好,以至于每天他们中的一个(从所有 $$$n$$$ 学生中随机选择的)都会生气。生气的学生会做以下事情之一。
- 以 $$$\frac 1 2$$$ 的概率,他离开当前的俱乐部,然后自己创建一个新俱乐部并加入它。他创建的新社团里只有一名学生(他自己)。
- 以 $$$\frac 1 2$$$ 的概率,他不会创建新俱乐部。在这种情况下,他将他的俱乐部更换为一个新俱乐部(可能是他当前所在的同一俱乐部),其概率与该俱乐部中的学生数量成正比。正式地,假设有 $$$k$$$ 俱乐部,并且第 $$$i$$$ 俱乐部中有 $$$b_i$$$ 学生,$$$1 \leq i \leq k$$$ (在学生生气之前)。他离开当前的俱乐部,然后以 $$$\frac {b_i} {n}$$$ 的概率加入第 $$$i$$$ 个俱乐部。
Homer 想知道每个学生第一次进入同一俱乐部的预计天数。
我们可以证明答案可以表示为有理数 $$$\frac p q$$$ 且 $$$\gcd(p, q) = 1$$$。因此,要求您求 $$$pq^{-1} \bmod 998\,244\,353$$$ 的值。可以证明,在给定的问题约束下, $$$q \bmod 998\,244\,353 \neq 0$$$ 。
输入
第一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 1000$$$) — 最初的俱乐部数量。
第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \leq a_i \leq 4 \cdot 10^8$$$) 和 $$$1 \leq a_1+a_2+\dots+a_m \leq 4 \cdot 10^8$$$,其中$$$a_i$$$ 表示最初第 $$$i$$$ 个俱乐部的学生人数。
输出
打印一个整数 - 每个学生第一次进入同一俱乐部的预期天数,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 1 1
输出 #1
4
输入 #2
2 1 2
输出 #2
18
输入 #3
3 1 1 1
输出 #3
21
输入#4
1 400000000
输出#4
0
输入 #5
10 1 2 3 4 5 6 7 8 9 10
输出 #5
737609878
注意
在第一个例子中,无论哪个学生生气,这两个学生都会以 $$$\frac 1 4$$$ 的概率进入同一个俱乐部。因此,每个学生加入同一俱乐部的预计天数应为 $$$4$$$。
在第二个示例中,我们注意到在第一天:
- 第一个俱乐部中唯一的学生会生气,概率为 $$$\frac 1 3$$$。如果他生气了,那么他会创建一个新俱乐部,并以 $$$\frac 1 2$$$ 的概率加入(在这种情况下,将有三个俱乐部,分别有 $$$0, 1, 2$$$ 学生),离开当前俱乐部并以 $$$\frac 1 2 \cdot \frac 2 3 = \frac 1 3$$$ 的概率加入第二个俱乐部,或者以 $$$\frac 1 2 的概率保持不动\cdot \frac 1 3 = \frac 1 6$$$;
- 第二个俱乐部的两名学生中的每一个都会生气,概率为 $$$\frac 1 3$$$。如果其中一人生气,那么他将创建一个新俱乐部并以 $$$\frac 1 2$$$ 的概率加入该俱乐部,以 $$$\frac 1 2 \cdot \frac 1 3 = \frac 1 6$$$ 的概率离开当前俱乐部并加入第二个俱乐部,或者以 $$$\frac 1 2 \cdot \frac 2 3 = \frac 1 3$$$ 的概率保持不动。
在第四个示例中,最初只有一个俱乐部。也就是说,每个学生都已经加入过同一个俱乐部。所以答案是$$$0$$$。