시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 3 | 3 | 3 | 100.000% |
Given are $n$ prime numbers $1 < p_1 < p_2 < \ldots < p_n < 10^{18}$ with $p_1 \le 100$. We say that the number $x$ is good if $x$ is divisible by at least one $p_i$.
Take all good numbers $a_1, a_2, \cdots, a_m$ in $[0, p_1 \cdot p_2 \cdot \ldots \cdot p_n]$ and sort them in order ($a_1 < a_2 < \ldots < a_m$). Your task is to calculate $\sum_{i=1}^{m-1} (a_{i+1} - a_i)^2$. As the sum could be very large, you should output it modulo $998\,244\,353$.
The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$).
The next line of the input contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 < p_1 < p_2 < \ldots < p_n < 10^{18}$). It is guaranteed that $2 \le p_1 < 100$ and each $p_i$ ($1 \le i \le n$) is a prime number.
Output a single line with a single integer, indicating the answer modulo $998\,244\,353$.
2 2 5
18
3 5 7 233
31275
In the first example, the list of good numbers is:
Thus, the answer is $(2-0)^2+(4-2)^2+(5-4)^2+(6-5)^2+(8-6)^2+(10-8)^2=18$.