您正在玩最大公约数牌组构牌游戏 (GCDDCG)。有 $$$N$$$ 卡(编号从 $$$1$$$ 到 $$$N$$$)。卡 $$$i$$$ 的值为 $$$A_i$$$,它是 $$$1$$$ 和 $$$N$$$(含)之间的整数。
游戏由 $$$N$$$ 轮组成(编号从 $$$1$$$ 到 $$$N$$$)。在每一轮中,您需要构建两个非空牌组,牌组 $$$1$$$ 和牌组 $$$2$$$。一张牌不能同时存在于两副牌中,并且允许不使用所有$$$N$$$牌。在 $$$i$$$ 轮中,每副牌中牌值的最大公约数 (GCD) 必须等于 $$$i$$$。
您在 $$$i$$$ 回合中的创造力点是 $$$i$$$ 与构建两副有效牌组的方法数量的乘积。如果其中一副牌包含不同的牌,则两种方式被认为是不同的。
求所有 $$$N$$$ 轮的创造力点总和。由于总和可能非常大,因此计算总和对 $$$998\,244\,353$$$ 取模。
输入
第一行由整数 $$$N$$$ ($$$2 \leq N \leq 200\,000)$$$ 组成。
第二行由 $$$N$$$ 整数 $$$A_i$$$ ($$$1 \leq A_i \leq N$$$) 组成。
输出
输出一个整数,表示所有 $$$N$$$ 轮的创造力点总和,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 3 3 3
输出 #1
36
输入 #2
4 2 2 4 4
输出 #2
44
输入 #3
9 4 2 6 9 7 7 7 3 3
输出 #3
10858
注意
示例输入/输出#1 的说明
每轮$$$1$$$和$$$2$$$的创造力点是$$$0$$$。
在 $$$3$$$ 回合中,有 $$$12$$$ 方法来构建两套牌。将 $$$B$$$ 和 $$$C$$$ 分别表示为牌组 $$$1$$$ 和牌组 $$$2$$$ 中的卡号集合。构建两套牌的 $$$12$$$ 方法是:
- $$$B = \{ 1 \}, C = \{ 2 \}$$$;
- $$$B = \{ 1 \}, C = \{ 3 \}$$$;
- $$$B = \{ 1 \}, C = \{ 2, 3 \}$$$;
- $$$B = \{ 2 \}, C = \{ 1 \}$$$;
- $$$B = \{ 2 \}, C = \{ 3 \}$$$;
- $$$B = \{ 2 \}, C = \{ 1, 3 \}$$$;
- $$$B = \{ 3 \}, C = \{ 1 \}$$$;
- $$$B = \{ 3 \}, C = \{ 2 \}$$$;
- $$$B = \{ 3 \}, C = \{ 1, 2 \}$$$;
- $$$B = \{ 1, 2 \}, C = \{ 3 \}$$$;
- $$$B = \{ 2, 3 \}, C = \{ 1 \}$$$;和
- $$$B = \{ 1, 3 \},C = \{ 2 \}$$$。
示例输入/输出#2 的说明
对于 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 轮,分别有 $$$0$$$、$$$18$$$、$$$0$$$ 和 $$$2$$$ 构建两套牌的方法。