题目描述

小 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 $ 取模的结果。

样例

input

3
1 2 3

output

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 $。