#6703. 小 Q 的序列

题目描述

小 Q 喜欢在序列上数数。

定义一个序列 $a_1...k$ 的权值为 $\prod_{i=1}^{k}(a_i + i)$。

现在小 Q 有一个长度为 $n$ 的序列 $c_1...n$。他想知道他的序列的所有 $2^n - 1$ 个非空子序列的权值和。

由于答案很大，你只需要输出答案对 998244353 取模的结果。

输入格式

第一行，一个正整数 $n$。接下来一行，$n$ 个非负整数，代表长度为 $n$ 的序列 $c_1...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$。