Counting Unique Height Sequences

CleverRaccoon is fascinated by the ever-changing heights of the maple creek stones. Given two integers n and m, you are to determine how many distinct height sequences can be formed under the following constraints:

Constraints

• If n > 1 (i.e. the sequence has length greater than 1):
• The first and last elements, \(a_1\) and \(a_n\), can be any integer in the range \([0, m]\).
• For every other element \(a_i\) with \(2 \le i \le n-1\), the allowed range is \([0, m-1]\).
• If n = 1 (i.e. the sequence has only one element):
• The element \(a_1\) can be any integer in the range \([0, m+1]\).

Equivalence of Sequences

Two sequences \(a = (a_1, a_2, \ldots, a_n)\) and \(b = (b_1, b_2, \ldots, b_n)\) are considered identical if either:

• \(a_i = b_i\) for all \(i = 1, 2, \ldots, n\), or
• \(a_i = b_{n-i+1}\) for all \(i = 1, 2, \ldots, n\) (i.e. one sequence is the reverse of the other).

Task

Calculate the maximum number of different sequences modulo \(998244353\).

Mathematical Formulation

• If \(n = 1\): The total number of valid sequences is \(m+2\).
• If \(n > 1\):
  • Let \(T = (m+1)^2 \cdot m^{n-2}\) be the total number of sequences (before considering symmetry).
  • Let \(P\) be the number of palindromic sequences (i.e. sequences that are the same when reversed). Then:
    • If \(n\) is even, say \(n=2k\), then \(P = (m+1) \cdot m^{k-1}\).
    • If \(n\) is odd, say \(n=2k+1\), then \(P = (m+1) \cdot m^{k}\).
  • The answer is given by:
    \(\text{Answer} = \frac{T + P}{2} \;\bmod\; 998244353\).

Note: All exponentiations and multiplications are performed modulo \(998244353\).

inputFormat

The input consists of a single line containing two integers n and m.

For example:

3 2

outputFormat

Output a single integer: the maximum number of distinct sequences modulo 998244353.

sample

1 1

3