Kim's Quest

In the long-forgotten halls of Kombinatoria's ancient academy, a gifted mathematician named Kim faces an unusual challenge. Kim found an old sequence of integers, believed to be a cryptic message from the legendary Kombinatoria's Oracle, and wants to decipher its hidden meaning.

Kim's mission is to find specific patterns within the sequence, called Harmonious Subsequences. A Harmonious Subsequence is one in which the sum of every three consecutive numbers is even, and it has at least three numbers.

Given a sequence $a_i$ ($1 \le i \le n$) of length $n$, a subsequence of length $m$ is $a_{b_1}, a_{b_2}, \ldots, a_{b_m}$, uniquely defined by a set of $m$ indices $b_j$ with $1 \le b_1 < b_2 < \ldots < b_m \le n$. Subsequences given by different index sets are considered different.

The number of these subsequences can be very large. Kim must report the total number of Harmonious Subsequences modulo $998\,244\,353$.

The first line contains a single integer $n$, the length of the sequence ($3 \le n \le 2 \cdot 10^5$).

The second line contains $n$ space-separated integers $a_i$, the elements of the sequence ($1 \le a_i \le 2 \cdot 10^5$).

Output one number, the number of Harmonious Subsequences modulo $998\,244\,353$.

In the statement's fifth sample, the sequence is split across three lines for readability, but in the actual test data it is given on one line. The actual number of Harmonious Subsequences there is $4\,991\,221\,765 = 5 \times 998\,244\,353$, so the output is zero after taking the remainder modulo $998\,244\,353$.