在 Kombinatoria 古老学院那被遗忘的殿堂里，一位名叫 Kim 的天才数学家面临着一项不同寻常的挑战。他们发现了一个古老的整数序列，据信这是来自传说中 Kombinatoria 神谕的神秘信息，Kim 希望破译其隐藏的含义。

Kim 的任务是在序列中寻找特定的模式，即“和谐子序列”（Harmonious Subsequences）。这些特殊的子序列满足以下条件：序列中任意三个连续数字之和均为偶数，且每个子序列的长度至少为 3。

给定一个长度为 $n$ 的序列 $a_i$ ($1 \le i \le n$)，其长度为 $m$ 的子序列为 $a_{b_1}, a_{b_2}, \dots, a_{b_m}$，由一组下标 $b_j$ 唯一确定，满足 $1 \le b_1 < b_2 < \dots < 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$ 取模。

样例

样例输入 1

3
1 2 3

样例输出 1

1

样例输入 2

5
2 8 2 6 4

样例输出 2

16

样例输入 3

5
5 7 1 3 5

样例输出 3

0

样例输入 4

11
3 1 4 1 5 9 2 6 5 3 6

样例输出 4

386

样例输入 5

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

样例输出 5

0

说明

在第五个样例提供的输入数据中，为了清晰起见，序列被分成了三行，但应当理解在实际测试数据中，序列是写在同一行中的。该样例中和谐子序列的实际数量为 $4\,991\,221\,765 = 5 \times 998\,244\,353$，因此输出结果为该数值除以 $998\,244\,353$ 后的余数，即 0。