Sum of Distinct Subsequences in Subarrays

Charlie has a sequence ( a = [a_1, a_2, a_3, \ldots, a_n] ). For any interval ( [l, r] ) with ( 1 \le l \le r \le n ), let ( a[l:r] = [a_l, a_{l+1}, \ldots, a_r] ) denote the contiguous subarray from position ( l ) to ( r ). A subsequence of ( a[l:r] ) is any sequence ( [a_{i_1}, a_{i_2}, \ldots, a_{i_k}] ) where ( l \le i_1 < i_2 < \cdots < i_k \le r ). Note that the empty sequence is also considered a subsequence. Two subsequences are considered essentially different if they have different lengths or differ in at least one corresponding element.

For a given interval ( [l, r] ), define ( F(l, r) ) as the number of essentially different subsequences of ( a[l:r] ) (including the empty subsequence). For example, if ( a = [1, 9, 9] ), then for the interval ( [1, 3] ): [ \begin{aligned} \text{dp}[0] &= 1 \quad (\text{empty subsequence})\ \text{dp}[1] &= 2 \quad ([1])\ \text{dp}[2] &= 4 \quad ([9] and [1,9])\ \text{dp}[3] &= 6 \quad ([9,9] and [1,9,9]) \end{aligned} ] so ( F(1, 3) = 6 ).

Your task is to compute the sum: [ S = \sum_{1 \le l \le r \le n} F(l, r) \mod 998244353, ] where ( 998244353 = 7 \times 17 \times 2^{23} + 1 ) is a prime number.

Input Format: The first line contains a single integer ( n ) denoting the length of the sequence. The second line contains ( n ) space-separated integers, representing the sequence ( a ).

Output Format: Output a single integer, the value of ( S ) modulo ( 998244353 ).

inputFormat

The first line contains an integer n (the length of the sequence). The second line contains n space-separated integers representing the sequence a.

outputFormat

Output a single integer representing the sum \( \sum_{1 \leq l \leq r \leq n} F(l, r) \) modulo 998244353.

sample

1
1

2