#6703. 小 Q 的序列

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

题目描述

小 Q 喜欢在序列上数数。

定义一个序列 a_{1\ldots k} 的权值为 \prod_{i = 1}^k(a_i + i)

现在小 Q 有一个长度为 n 的序列 c_{1\ldots n} 。 他想知道他的序列的所有 2^n - 1 个非空子序列的权值和。
由于答案很大,你只需要输出答案对 998244353 取模的结果。

输入格式

第一行,一个正整数 n 。 接下来一行, n 个非负整数,代表长度为 n 的序列 c_{1\ldots n}

输出格式

一行,一个非负整数,答案对 998244353 取模的结果。

样例

样例输入

3
1 2 3

样例输出

90

数据范围与提示

对于 25\% 的分数, 1 \leq n \leq 1000

对于另外 25\% 的分数, c_i (1 \leq i \leq n) 为等差数列且公差为 \pm 1

对于所有数据: 1 \leq n \leq 100000 ,对于 1 \leq i \leq n ,有 0 \leq c_i \leq 998244352