在 Kombinatoria 古老学院的长期被遗忘的大厅里,一位名叫 Kim 的天才数学家面临着一个不寻常的挑战。他们发现了一个旧的整数序列,这被认为是来自传奇的 Kombinatoria 甲骨文的神秘消息,金想要破译其隐藏的含义。
Kim 的任务是找到序列中的特定模式,称为 和谐的子序列。这些是非凡的子序列,其中每三个连续数字的总和为偶数,并且每个子序列的长度必须至少为三个数字。
给定一个长度为 $$$n$$$ 的序列 $$$a_i$$$ ($$$1 \le i \le n$$$),其 子序列 长度为 $$$m$$$ 的 等于 $$$a_{b_1}, a_{b_2}, \ldots, a_{b_m}$$$ 并且由一组 $$$m$$$ 索引 $$$b_j$$$ 唯一定义,使得 $$$1 \le b_1 \lt b_2 \lt \ldots \lt b_m \le n$$$。由不同索引集 $$$b_j$$$ 给出的子序列被认为是不同的。
Kim 的探索有一个转折:这些和谐子序列的数量可能会令人难以承受。为了有效地报告结果,Kim 必须计算这些子序列的总数,将答案表示为除以数字 $$$998\,244\,353$$$ 后的余数。
输入
第一行包含一个整数 $$$n$$$ — 序列的长度 ($$$3 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_i$$$ — 序列的元素 ($$$1 \le a_i \le 2 \cdot 10^5$$$)。
输出
输出一个数字——和谐子序列的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
31 2 3
输出复制
1
输入复制
52 8 2 6 4
输出复制
16
输入复制
55 7 1 3 5
输出复制
0
输入复制
113 1 4 1 5 9 2 6 5 3 6
输出复制
386
输入复制
54 2 1 1 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 1 1 1 1 2 2 1 1 2 2 2 2 2 1 1 1 2 2 1 2 1 1
输出复制
0
注意
在为第五个样本提供的输入数据中,为了清楚起见,数字序列被分成三行,但应该理解的是,在实际测试数据中,序列是在一行中给出的。本例中和谐子序列的实际数量为 $$$4\,991\,221\,765 = 5 \times 998\,244\,353$$$,因此除以数字 $$$998\,244\,353$$$ 后求余数,结果输出为零。