← 返回题目列表

AtCoder · arc192_d

D. 分数线

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

分数: 600 点

问题陈述

对于正有理数 x,定义 f(x) 如下:

快递 x as \dfrac{P}{Q} 使用互质正整数 P 和 Q. f(x) 定义为值 P\times Q.

给你一个正整数 N 和一个序列 A=(A_1,A_2,\dots,A_{N-1}) 长度为正整数 N-1.

我们称序列 S=(S_1,S_2,\dots,S_N) 长度为正整数 N a 好的序列 如果满足以下所有条件:

  • 对于每个整数 i 与 1\leq i\leq N-1,它认为 序列的 f\left(\dfrac{S_i}{S_{i+1}}\right)=A_i.
  • \gcd(S_1,S_2,\dots,S_N)=1.

定义 分数 本实验的 作为其所有元素的乘积。

可以证明好序列的数量是有限的。求总和,取模 998244353,所有良好序列的分数。

约束

  • 2\leq N\leq 1000
  • 1\leq A_i\leq 1000 (1\leq i\leq N-1)
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \dots A_{N-1}

输出

打印总和,模数 998244353,所有良好序列的分数。


示例输入 1

6
1 9 2 2 9

示例输出 1

939634344

例如,两者 (2,2,18,9,18,2) 和 (18,18,2,1,2,18) 都是很好的序列,并且得分均为 23328.

共有 16 好的序列,所有序列的分数总和为 939634344.


示例输入 2

2
9

示例输出 2

18

有 2 良好的序列,得分均为 9.


示例输入 3

25
222 299 229 22 999 922 99 992 22 292 222 229 992 922 22 992 222 222 99 29 92 999 2 29

示例输出 3

192457116

不要忘记计算求和模 998244353.