#1209. Day4G. ZJY 心想绝对不能放你一马

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JamesHelium

题目描述

自渡渡鸟幼儿园之役以来,已经过了许久了。ZJY 也即将迎来生命的结束。在他风烛残年之际,猛然回想起在幼儿园里偶尔翻见的《数论魔导学指南》(Prof. Cretaceous 著),里面提到一种可以延长生命的法阵。

为了开启这种法阵,需要 星烛。一支 星烛拥有 条烛芯,在圆柱形的烛体上围绕成一个完美的圆,或者, 边形。在一支 星烛上,任意两根烛芯之间都有一缕微妙的光束连接,形成一颗牢不可破的星。我们称这种联系为“互感”。

ZJY 跟从魔导书的建议,收集了 支星烛,这 支星烛大小不一,第 支拥有 根烛芯。ZJY 把这些星烛按序排成一个环形,首尾相接。神奇的是,环上每相邻的两支星烛之间,最近的烛芯,也产生了互感!现在,这个法阵便是由 支互感连接的 颗星。

CvnED.jpg

业已耋耄之年的你来到了法阵前,心想决不能再让 ZJY 存续下去,否则你将受到更大的折磨。

为了破坏法阵,你必须破坏任意数量的互感,致使法阵里再也不可能出现互感形成的环。ZJY 为了打破你的阴谋,他必须知道有多少种不同的方法可以打破法阵。

答案可能很大,所以这是你今天第一次需要模 998244353

输入格式

第一行一个整数,表示星烛的数量

接下来一行 个数,表示星烛的烛芯数量

输出格式

一个整数,表示答案,需要模 998244353

样例

输入样例

3
3 3 3

输出样例

2680

数据范围与提示