题目描述

现在 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$ 取模。

3
3 1 2

332748118

提示

样例解释：

$1$ 号点有 $3$ 个棋子，$2$ 号点有 $1$ 个棋子，$3$ 号点有 $2$ 个棋子。第一次操作的时候，能进行的有三种可能：将 $2$ 号点的 $1$ 个棋子移到 $1$ 号点，将 $3$ 号点的 $1$ 个棋子移到 $1$ 号点，将 $3$ 号点的 $2$ 个棋子移到一号点。而其中只有一种情况能使得 Yopilla 有必胜策略。所以答案为

对于 $20 \%$ 的数据，只有一个石子。

对于 $100 \%$ 的数据，$1 \le n \le {10} ^ 6, 0 \le a_i \le {10} ^ 9$ ，保证至少有一个不在一号点的石子。