Problem Description

For a sequence \( (v_1, v_2, \dots, v_k) \) consisting of numbers from \( 1, 2, \dots, m \) and a function \( f: \{1, \dots, m\} \to \{1, \dots, m\} \), we say that \( f \) reverses \( (v_1, v_2, \dots, v_k) \) if it satisfies the following condition:

• The sequence \( (f(v_1), f(v_2), \dots, f(v_k)) \) is the same as the reversed sequence \( (v_k, v_{k-1}, \dots, v_1) \).

You are given a sequence \( (a_1, a_2, \dots, a_n) \) consisting of numbers from \( 1, 2, \dots, m \). There are \( \frac{n(n+1)}{2} \) non-empty contiguous subsequences of this sequence. For each of these subsequences, count how many functions exist that reverse them, and find the sum of these counts modulo \( 998244353 \).

Input Format

The input is given from the standard input in the following format:

\( n \) \( m \) \( a_1 \) \( a_2 \) \( \dots \) \( a_n \)

Output Format

Output the sum of the counts of reversing functions for each contiguous subsequence, modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

3 3
1 1 2

Sample Output #1

39

Sample Input #2

20 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Sample Output #2

326566600

Sample Input #3

46 128
109 98 111 106 103 46 51 46 58 50 49 51 106 102 108 108 106 111 48 116 117 116 102 117 111 112 100 48 113 107 47 115 102 101 112 100 117 98 48 48 59 116 113 117 117 105

Sample Output #3

249064602

Notes/Hints

Note

• For functions \( f \) and \( g \), if there exists an \( i \in \{1, \dots, m\} \) such that \( f(i) \neq g(i) \), \( f \) and \( g \) are considered different functions.

Constraints

• \( 1 \leq n, m \leq 3 \times 10^5 \)
• For each \( i = 1, 2, \dots, n \), \( 1 \leq a_i \leq m \)
• All inputs are integers.

Sample Explanation 1

The contiguous subsequences of the sequence \( (1, 1, 2) \) are \( (1) \), \( (1, 1) \), \( (1, 1, 2) \), \( (1) \), \( (1, 2) \), and \( (2) \).

• The necessary and sufficient condition for function \( f \) to reverse the sequence \( (1) \) is \( f(1) = 1 \), and there are 9 such functions on \( \{1, 2, 3\} \).
• The necessary and sufficient condition for function \( f \) to reverse the sequence \( (1, 1) \) is \( f(1) = 1 \), and there are 9 such functions on \( \{1, 2, 3\} \).
• The necessary and sufficient condition for function \( f \) to reverse the sequence \( (1, 1, 2) \) is \( f(1) = 2 \), \( f(1) = 1 \), and \( f(2) = 1 \), and there are no such functions.
• The necessary and sufficient condition for function \( f \) to reverse the sequence \( (1, 2) \) is \( f(1) = 2 \) and \( f(2) = 1 \), and there are 3 such functions on \( \{1, 2, 3\} \).
• The necessary and sufficient condition for function \( f \) to reverse the sequence \( (2) \) is \( f(2) = 2 \), and there are 9 such functions on \( \{1, 2, 3\} \).

Thus, the answer is \( 9 + 9 + 0 + 9 + 3 + 9 = 39 \).

Sample Explanation 2

Remember to take the modulo \( 998244353 \).

见题面 Input 部分

见题面 Output 部分