题目描述

$Bob$ 最近对数塔很感兴趣，给定 $n$ 个整数作为数塔第一层，从第二层开始每个数字都是下一层相邻两个数字之和，如下图：

$Bob$ 想知道塔顶（即第 $n$ 层）数字是多少？由于数字之和很大，请输出 $998244353$ 的余数。

输入格式

第一行，一个整数 $n$

第二行，$n$个整数, 第 $i$ 个整数 $a_i$

输出格式

一个正整数，表示塔顶数字取 $998244353$ 的余数

注意：由于输入有负数，需要输出求余后的正数。

4
5 16 7 8

82

4
5 -16 7 8

998244339

数据规模与约定

所有测试数据满足：$2 \le n \le 10^4, -10^9 \le a_i \le 10^9$

其中 $20\%$ 的测试数据满足：$2 \le n \le 10, 0 \le a_i \le 10$

其中 $20\%$ 的测试数据满足：$2 \le n \le 10, 0 \le a_i \le 10^9$

其中 $40\%$ 的测试数据满足：$2 \le n \le 10^3, -10^9 \le a_i \le 10^9$

另外 $20\%$ 的测试数据满足：$2 \le n \le 10^4, -10^9 \le a_i \le 10^9$