#P12394. Good Tuple Sequences

    ID: 14497 Type: Default 1000ms 256MiB

Good Tuple Sequences

Good Tuple Sequences

We call a sequence of n intervals $$([l_1,r_1],[l_2,r_2],\dots,[l_n,r_n])$$ defined on the integer domain $${1,2,\dots,V}$$ (i.e. $$1\le l_i\le r_i\le V$$ for every $$1\le i\le n$$) a good sequence if and only if for every pair of indices $$1\le i<j\le n$$ one of the following holds:

  1. The intervals are nested, that is,
ljlirirj,l_j\le l_i\le r_i\le r_j,
  1. They are disjoint, that is, either
rj<liorri<lj.r_j < l_i \quad\text{or}\quad r_i < l_j.

In other words, every pair of intervals either do not intersect at all or one of them is contained in the other (with the containing interval coming later in the sequence).

Given two integers n and m, for every $$V=1,2,\dots,m$$ let $$f(n,V)$$ be the number of good sequences of n intervals with endpoints chosen from $${1,2,\dots,V}$$. Your task is to compute

V=1mf(n,V)(mod998244353).\sum_{V=1}^{m} f(n,V) \pmod{998244353}.

Note that all formulas above are in (\LaTeX) format.

inputFormat

The first and only line of input contains two integers n and m.

Constraints: n and m are small enough so that a recursive DP solution runs in time.

outputFormat

Output a single integer, the value of $$\sum_{V=1}^{m} f(n,V)$$ modulo 998244353.

sample

1 1
1