← 返回题目列表

AtCoder · arc134_e

E. 尼姆模

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

Snuke 发现了一块黑板,上面什么也没写。

他会做 N 在这块黑板上进行操作。 在 i-th 操作,他选择一个整数 1 和 a_i (含)并写在黑板上。

之后 黑板上写着 N 整数,一太郎和二郎二就会用它玩游戏。 游戏中,两人交替进行以下操作,第一太郎先进行。

  • 让 X 是黑板上写的最大整数。
    • If X=0,当前玩家 获胜 游戏结束。
  • 选择一个整数 m 之间 1 和 X (含)。
  • 替换每个 N 写在黑板上的整数及其除以的余数 m.

有 \prod_{i=1}^{N}a_i Snuke 在黑板上写数字的方法。如果两位玩家都发挥最佳,找出其中导致太郎一世获胜的方法的数量,取模 998244353.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 200
  • 1 \leq a_i \leq 200

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 \cdots a_N

输出

打印整数写入方式的数量,如果两个玩家都发挥最佳,则将导致太郎一世获胜,模数 998244353.


示例输入 1

1
3

示例输出 1

1
  • 只有 Snuke 写入,Taro First 才会获胜 3.
  • 否则,老太郎只能下出使黑板上的整数为整数的棋步 0.

示例输入 2

2
5 10

示例输出 2

47

示例输入 3

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

示例输出 3

273710435
  • 一定要找到计数模数 998244353.