#R2024A0703. 差分塔

差分塔

差分塔

题目背景

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

题目内容

现有一个长度为 nn 的序列 AA ,其中第 ii 个元素为 aia_i

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

输入格式

第一行一个正整数 nn ,表示序列的长度。

第二行 nn 个正整数表示 aia_i

输出格式

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

测试样例

输入
6
1 18 27 50 67 99
输出
83

数据范围

1n1e61\leq n \leq1e61ai1e91\leq a_i \leq 1e9