Description

在康比纳托里亚古老学院被遗忘的大厅里，一位名叫金姆的天才数学家面临着一个不寻常的挑战。他们发现了一个古老的整数序列，据信这是来自传奇的康比纳托里亚神谕的加密信息，金姆想要破译其中隐藏的含义。

金姆的任务是在序列中寻找特定的模式，这些模式被称为和谐子序列。这些特殊的子序列需要满足每三个连续数字之和为偶数，且每个子序列的长度必须至少为三个数字。

给定一个长度为 $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 < b_2 < \ldots < b_m \le n$。由不同索引集 $b_j$ 给出的子序列被视为不同的子序列。

金姆的探索有一个转折：这些和谐子序列的数量可能非常庞大。为了有效地报告发现结果，金姆必须计算这些子序列的总数，并将答案对 $998\,244\,353$ 取模后输出。

Input Format

第一行包含一个整数 $n$ —— 序列的长度（$3 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个用空格分隔的整数 $a_i$ —— 序列的元素（$1 \le a_i \le 2 \cdot 10^5$）。

Output Format

输出一个数字 —— 和谐子序列的数量，对 $998\,244\,353$ 取模后的结果。

3
1 2 3

1

5
2 8 2 6 4

16

5
5 7 1 3 5

0

11
3 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

Hint

在第五个样例的输入数据中，数字序列被分成三行以提高可读性，但在实际的测试数据中，序列是以一行给出的。在这个例子中，实际的和谐子序列数量为 $4\,991\,221\,765 = 5 \times 998\,244\,353$，因此输出为零，因为这是其对 $998\,244\,353$ 取模后的结果。

翻译由 DeepSeek V3 完成