题目描述

「诶，我想生成一个随机数，等概率是 $1$ 或 $2$。」

「呐，我给你一枚均匀的硬币，你扔一次就好啦。」

「那如果我想让它等概率是 $1$ 或 $2$ 或 $3$ 呢？」

「嗯，我想想。这样吧，你先扔两次，如果依次是反反就生成 $1$，反正就生成 $2$，正反就生成 $3$，正正就重新来吧。」

「诶，这个方案是不是有可能永远不能结束啊？」

「是的呢，但是期望 $\frac{8}{3}$ 次就可以结束了，而且这是期望次数最小的方案。」

「好厉害呀。那如果我还是想让它是 $1$ 或 $2$，但是概率比是 $1$ 比 $2$ 呢？」

「还是可以用刚才的方案，如果生成了 $3$ 就当成 $2$ 好了。」

「啊，那在这里还是期望次数最小的方案吗？」

「应该不是了吧，毕竟浪费了一些信息。」

「那么应该是什么方案呢？」

「似乎有点复杂了呢，让我想一想。」

从前有一个随机数生成器，能够生成一个 $[1,n]$ 内的整数，且生成 $i$ 的权重是 $a_i$（即生成 $1\ldots n$ 的概率比是 $a_1:a_2:\ldots :a_n$）。现在它已经找不到了，而你想模拟这个生成的过程，但是你手里只有一枚均匀的硬币。你想了很久，设计了一个方案并开始扔硬币。可是你扔了很多很多次硬币，却发现你还是没有模拟成功——或许这个方案实在太慢了，甚至有可能永远不会结束。于是你希望找到一个期望扔硬币次数最少的模拟方案，但是这个方案讲起来可能比较复杂，你想先知道这个最少的期望扔硬币次数。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个空格隔开的正整数，其中第 $i$ 个数是 $a_i$。

输出格式

我们保证这个答案是一个正有理数，设其等于 $\frac{P}{Q}$，且 $P$ 和 $Q$ 是互质的正整数。

我们保证存在非负整数 $R$，使得 $P$ 和 $R\times Q$ 对 $998244353$ 取余的结果相等，设 $S$ 是最小的 $R$。

仅一行，一个非负整数 $S$。

样例 1

2
1 1

1

$P=1,Q=1$，方案见题目背景。

3
1 1 1

665496238

$P=8,Q=3$，方案见题目背景。

2
1 3

499122178

$P=3,Q=2$，方案是如果第一次正面则直接生成 $2$，否则根据第二次来生成 $1$ 或 $2$。

7
1 1 1 1 1 1 1

570425348

$P=24,Q=7$，方案略。

3
2 3 3

748683267

$P=9,Q=4$，方案略。

3
1 3 5

887328316

$P=20,Q=9$，方案略。

3
3 3 4

798595485

$P=13,Q=5$，方案略。

数据范围与提示

测试点编号	规模限制	特殊限制
$1$	$n=2$	A
$2,3$		B
$4$		无
$5$	$n=m$	A
$6,7$		B
$8$		无
$9$	$m\le 10^3$	A
$10,11$		B
$12$		无
$13$	$m\le 10^5$	A
$14,15$		B
$16$		无
$17$	无	A
$18,19$		B
$20$		无

对于所有数据，$n\leq 10^6$，$m\leq 10^7$。其中 $m$ 表示所有 $a_i$ 的和，A 表示 $m$ 是 $2$ 的幂次，B 表示 $m$ 是奇数。