Displaying Decimals
After the BRICS group introduced the International Common Payment Currency (ICPC), all currencies (like real, peso, dollar, etc.) are now defined by their values in ICPCs.
To help people navigate this new world order, you decided to create a website to compute the conversion rates between currencies. The website handles $N$ currencies, numbered from $1$ to $N$. Each currency $i$ has an associated integer value $A_i$, indicating that one unit of currency $i$ is worth $A_i$ ICPCs.
The website works as follows: the user selects a source currency $i$, then they select a target currency $j$ (it might be that $j = i$), and the website displays the conversion rate between them, that is, the exact decimal representation of $$\frac{A_i}{A_j}.$$
To deal with repeating decimals, you decided to display only the first period (represented by a line above it, when it exists). Thus, the quotient $\dfrac{4}{4}=1$ requires $1$ digit to be displayed, $\dfrac{4}{3}=1.3\overline{3}$ needs $2$ digits, $\dfrac{41}{4}=10.25$ uses $4$ digits, and $\dfrac{3}{14}=0.\overline{2142857}$ takes $8$ digits.
Your website has been running successfully for quite some time. As part of your performance analytics, you want to compute the expected display size of conversion rate pages.
Given the values $A_1, A_2, \ldots, A_N$, you must compute the expected number of digits needed to display the quotient $\dfrac{A_i}{A_j}$, when $i$ and $j$ are chosen uniformly at random between $1$ and $N$.
Input
The first line contains an integer $N$ ($1 \le N \le 10^5$) indicating the number of currencies.
The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^5$ for $i = 1, 2, \ldots, N$), where $A_i$ is the value of one unit of currency $i$ expressed in ICPCs.
Output
The expected number of digits needed to display the quotient $\dfrac{A_i}{A_j}$, when $i$ and $j$ are chosen uniformly at random between $1$ and $N$, can be expressed as an irreducible fraction $P/Q$, with $Q$ and $M = 998244353$ coprime. Let $Q^{-1}$ be the modular multiplicative inverse of $Q$ modulo $M$, that is, $Q \cdot Q^{-1} \equiv 1 \pmod{M}$. Output a single line with the integer $P \cdot Q^{-1} \bmod M$.
3 15 36 14
332748121
Explanation 1:
The table below shows the number of digits needed to display the quotients **row/column**, each of them with probability $1/36$.
| | 15 | 36 | 14 |
| 15 | 1 | 4 | 8 |
| 36 | 2 | 1 | 7 |
| 14 | 3 | 3 | 1 |
For example, $\frac{14}{36} \approx 0.38$ requires **3 digits** (the example in the original text is likely a typo and should be $\frac{10}{30}$ or $\frac{14}{36}$, resulting in 3 digits). The expected number of digits is $\frac{10}{3} = 3 \frac{1}{3}$.
That is, $P = 10$ and $Q = 3$.
Since $Q^{-1} \equiv 332748118 \pmod{998244353}$, the final answer to be printed is:
$$P \cdot Q^{-1} \pmod{M} = 10 \cdot 332748118 \pmod{998244353} = 332748121$$
2 7 100000
249561093