Description

Now Yopilla and yww are going to play a game.

They mark $n$ points on a straight line, numbered from left to right as $1, 2, ..., n$. Then they place some stones on each point: point $i$ has $a_i$ stones. Next, starting from Yopilla, the two players take turns. Whoever cannot make a move loses. Each move is:

The current player chooses a point $x$ that has stones, then chooses at least one stone from point $x$, and moves all chosen stones to point $x / prime$, where $prime$ is a prime number and $prime \mid x$.

Yopilla's strategy for the very first move is random: he randomly picks a point $x$ that has stones, randomly chooses a positive integer number of stones $y$, and randomly moves them to a reachable point $z$. All stones are considered identical. In other words, two moves are different if and only if the triple $(x, y, z)$ is different. After that, both players play with optimal strategies.

Yopilla wants to predict the probability that he can win. Output the answer modulo $998244353$.

Input Format

The first line contains one integer $n$.

The second line contains $n$ integers $a_1, a_2, ..., a_n$.

Output Format

Output one line, representing the probability that Yopilla can win modulo $998244353$.

3
3 1 2

332748118

Hint

Explanation of the sample:

Point $1$ has $3$ stones, point $2$ has $1$ stone, and point $3$ has $2$ stones. On the first move, there are three possible moves: move the $1$ stone at point $2$ to point $1$; move $1$ stone at point $3$ to point $1$; move $2$ stones at point $3$ to point $1$. Among these, only one case allows Yopilla to have a winning strategy. So the answer is

For $20\%$ of the testdata, there is only one stone.

For $100\%$ of the testdata, $1 \le n \le {10} ^ 6$, $0 \le a_i \le {10} ^ 9$. It is guaranteed that there is at least one stone not at point $1$.

Translated by ChatGPT 5