该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

chan和miku深夜交谈。

「诶，我想生成一个随机数，等概率是 $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$）。现在它已经找不到了，而chan想模拟这个生成的过程，但是chan手里只有一枚均匀的硬币。

chan想了很久，设计了一个方案并开始扔硬币。

可是chan扔了很多很多次硬币，却发现还是没有模拟成功（或许这个方案实在太慢了，甚至有可能永远不会结束）。于是chan希望找到一个期望扔硬币次数最少的模拟方案，但是这个方案讲起来可能比较复杂（搞方案的话这题就上NOI-难度了，我都不一定能写出标准程序），chan想先知道这个最少的期望扔硬币次数。

输入格式

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

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

输出格式

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

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

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

样例

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$。

数据的规模与约定

对于所有数据，$n\leq 10^6，m\leq 10^7$。其中 $m$ 表示所有 $a_i$ 的和

特殊性质：

• $A$ 表示 $m$ 是 $2$ 的幂次
• $B$ 表示 $m$ 是奇数。