题目描述

すぬけ君发现了一块什么都没写的黑板。

すぬけ君将在黑板上进行 $N$ 次操作。在第 $i$ 次操作中，他会选择并写下一个 $1$ 到 $a_i$ 之间的整数。

当黑板上写满 $N$ 个整数后，先手太郎君和后手次郎君将用这块黑板进行一个游戏。游戏由先手太郎君开始，双方轮流进行如下操作：

• 设黑板上写着的最大整数为 $X$。
  • 若 $X=0$，则当前轮到的玩家获胜，游戏结束。
• 选择一个 $1$ 到 $X$ 之间的整数（记为 $m$）。
• 将黑板上所有 $N$ 个整数都替换为它们除以 $m$ 的余数。

すぬけ君的写法共有 $\prod_{i=1}^{N} a_i$ 种可能，其中有多少种写法能让在两人都采取最优策略时，先手太郎君获胜？请将答案对 $998244353$ 取模后输出。

输入格式

输入以如下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\cdots$ $a_N$

输出格式

输出在两人都采取最优策略时，先手太郎君能获胜的写法数对 $998244353$ 取模的结果。

样例 1

输入

1
3

输出

1

样例 2

输入

2
5 10

输出

47

样例 3

输入

20
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200

输出

273710435

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 200$
• $1 \leq a_i \leq 200$

样例解释 1

• 只有当すぬけ君写下 $3$ 时，先手太郎君才能获胜。
• 其他情况下，先手太郎君只能让黑板上的整数都变为 $0$。

样例解释 3

• 别忘了对 $998244353$ 取模。

由 ChatGPT 4.1 翻译