$极限卡常题，慎入$

题目背景

$可爱捏$

题目描述

给出一个可重集$S$

求 $\sum_{s' \subset \ S}^{}[gcd(s')=1] \ \ mod \ \ 998244353$

$gcd(s)$是一个定义在集合上的函数，表示集合内所有数的最大公约数，空集的$gcd=0$,只有一个数的集合的$gcd$等于这个数

输入格式

输入$n$表示$|S|$

接下来输入$n$个数表示可重集$S$

输出格式

答案

样例 #1

样例输入 #1

3
1 2 4

样例输出 #1

4

提示

$n<=5*10^5$

对于每个$a_i \in S,a_i \in [1,5*10^5]$

每个$a_i$的出现次数不超过$10^4$