#P12394. Good Tuple Sequences
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:
- The intervals are nested, that is,
- They are disjoint, that is, either
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
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