该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

差分塔

题目背景

在大家最喜爱的算法中有这么一个算法叫差分。不算第一项的情况下，我们可以从一个长度为 $n$ 的序列 $A$ 中得到一个长度为 $n-1$ 的差分序列 $B$ ，其中的第 $i$ 项为 $b_i=a_{i+1}-a_i\quad ,1 \leq i \leq n-1$ 。我们可以发现，做过一次差分后得到的序列 $B$ 还可以继续做差分得到序列 $C$ ，直到最后只剩一个数。

题目内容

现有一个长度为 $n$ 的序列 $A$ ，其中第 $i$ 个元素为 $a_i$ 。

要求输出做过若干次差分后最后剩下的一个数在模 $998244353$ 后的结果。

输入格式

第一行一个正整数 $n$ ，表示序列的长度。

第二行 $n$ 个正整数表示 $a_i$ 。

输出格式

一个整数表示最后剩下的数。

测试样例

输入

6
1 18 27 50 67 99

输出

83

数据范围

$1\leq n \leq1e6$ ，$1\leq a_i \leq 1e9$