取石子

题目描述

现在 Yopilla 和 yww 要开始玩游戏! 他们在一条直线上标记了 $n$ 个点,从左往右依次标号为 $1, 2, ..., n$ 。然后在每个点上放置一些棋子,其中第 $i$ 个点放置了 $a_i$ 个棋子。接下来,从 Yopilla 开始操作,双方轮流操作,谁不能操作谁输。每次的操作是:当前操作方选定一个有棋子的点 $x$ ,然后选择至少一个点 $x$ 上的棋子,然后把这些棋子全都移动到点 $x / prime$ 上,其中 $prime$ 是一个质数,且 $prime \mid x$ 。 Yopilla 最初一次操作的策略是随机的:随机找到一个有棋子的点 $x$ ,随机选择正整数个棋子 $y$ ,随机转移到一个能转移到的点 $z$ 。所有棋子可以看作是一样的,换句话说:两种操作不同,当且仅当三元组 $(x, y, z)$ 不同。之后双方都按照最优策略来操作。 Yopilla 想要预测,他能够获胜的概率是多少,答案对 $998244353$ 取模。

输入输出格式

输入格式


第一行一个数 $n$ 。 第二行 $n$ 个数 $a_1, a_2, ..., a_n$ 。

输出格式


输出 $m$ 行,表示 Yopilla 能够获胜的概率对 $998244353$ 取模。

输入输出样例

输入样例 #1

3
3 1 2

输出样例 #1

332748118

说明

样例解释: $1$ 号点有 $3$ 个棋子,$2$ 号点有 $1$ 个棋子,$3$ 号点有 $2$ 个棋子。第一次操作的时候,能进行的有三种可能:将 $2$ 号点的 $1$ 个棋子移到 $1$ 号点,将 $3$ 号点的 $1$ 个棋子移到 $1$ 号点,将 $3$ 号点的 $2$ 个棋子移到一号点。而其中只有一种情况能使得 Yopilla 有必胜策略。所以答案为 $$\frac{1}{3} \equiv 332748118 \pmod {998244353}$$ 对于 $20 \%$ 的数据,只有一个石子。 对于 $100 \%$ 的数据,$1 \le n \le {10} ^ 6, 0 \le a_i \le {10} ^ 9$ ,保证至少有一个不在一号点的石子。