Chaneka 有一个数组 $$$[a_1,a_2,\ldots,a_n]$$$。最初,所有元素都是白色的。 Chaneka 将选择一个或多个不同的索引,并将这些所选索引处的元素涂成黑色。然后,她将选择索引是至少一个黑色元素索引的倍数的所有白色元素,并将这些元素着色为绿色。之后,她的分数是所有黑色和绿色元素中 $$$a_i$$$ 的最大值。
Chaneka 有 $$$2^n-1$$$ 种选择黑色索引的方法。求 Chaneka 选择黑色指数的所有可能方式的分数总和。由于答案可能非常大,请打印对 $$$998\,244\,353$$$ 取模的答案。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的大小。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$0\leq a_i\leq10^5$$$)。
输出
一个整数,表示 Chaneka 选择黑色索引的所有可能方式的分数总和,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 19 14 19 9
输出 #1
265
输入 #2
1 0
输出 #2
0
输入 #3
15 90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990
输出 #3
266012571
注意
在第一个示例中,以下是选择黑色索引的 $$$15$$$ 可能方法:
- 索引 $$$1$$$ 为黑色。索引 $$$2$$$、$$$3$$$ 和 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$ 为黑色。索引 $$$4$$$ 为绿色。其中最大值为$$$14$$$。
- 索引 $$$3$$$ 为黑色。其中最大值为$$$19$$$。
- 索引 $$$4$$$ 为黑色。其中最大值为$$$9$$$。
- 索引 $$$1$$$ 和 $$$2$$$ 为黑色。索引 $$$3$$$ 和 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$ 和 $$$3$$$ 为黑色。索引 $$$2$$$ 和 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$ 和 $$$4$$$ 为黑色。索引 $$$2$$$ 和 $$$3$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$ 和 $$$3$$$ 为黑色。索引 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$14$$$。
- 索引 $$$3$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$2$$$ 和 $$$3$$$ 为黑色。索引 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$2$$$ 和 $$$4$$$ 为黑色。索引 $$$3$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$3$$$ 和 $$$4$$$ 为黑色。索引 $$$2$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$、$$$3$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$19$$$。
总金额为 $$$19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$$$。