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

[AdditionalFile161.zip](file://AdditionalFile161.zip?type=additional_file)

#161. 乘法逆元 2

标签: 传统 | 时间限制: 500 ms | 内存限制: 512 MiB | 显示标签 通过: 1332 | 提交: 4194

题目描述

这可能是一道模板题。

给定 $n$ 个正整数 $a_i$，求每个数在模 $p$ 意义下的乘法逆元。

提示：请使用高效的读入方式。

输入格式

第一行一个整数 $n$。

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

输出格式

一行一个数，表示 $\sum_{i=1}^{n} a_i^{-1} \times 998244353^{n-i} \pmod p$

样例

输入

5
4 7 8 12 123456

输出

650798912

五个数的逆元分别是：

250000002
142857144
125000001
83333334
78351802

数据范围与提示

对于 100% 的数据，有 $1 \le n \le 5000000, 1 \le a_i < p, p = 10^9 + 7$

2019.8.20 新加数据一组