Ball Distribution Under Constraints

You are given n balls and m boxes. All the balls must be placed into the boxes. However, there are several distinct sets of restrictions on how the balls can be placed. The answer may be very large so output it modulo \(998244353\).

There are 12 cases (I to XII) as follows:

• I: The balls are all distinct and the boxes are all distinct. There is no further restriction. Answer: \(m^n\).
• II: The balls are distinct, the boxes are distinct, and each box can hold at most one ball. Answer: \(P(m, n) = m \times (m-1) \times \cdots \times (m-n+1)\) (if \(m \ge n\), otherwise 0).
• III: The balls are distinct, the boxes are distinct, and each box must contain at least one ball. Answer: \(\sum_{j=0}^{m} (-1)^j \binom{m}{j} (m-j)^n\) (if \(n \ge m\), otherwise 0).
• IV: The balls are distinct and the boxes are all identical. (Empty boxes are allowed.) Answer: \(\sum_{k=1}^{\min(m,n)} S(n,k)\) where \(S(n,k)\) are the Stirling numbers of the second kind.
• V: The balls are distinct, the boxes are identical, and each box can hold at most one ball. Answer: 1 if \(n\le m\) and 0 otherwise.
• VI: The balls are distinct, the boxes are identical, and each box must contain at least one ball. Answer: \(S(n,m)\) (if \(n \ge m\), otherwise 0).
• VII: The balls are identical and the boxes are distinct. Answer: \(\binom{n+m-1}{m-1}\).
• VIII: The balls are identical, the boxes are distinct, and each box can hold at most one ball. Answer: \(\binom{m}{n}\) if \(n \le m\) and 0 otherwise.
• IX: The balls are identical, the boxes are distinct, and each box must contain at least one ball. Answer: \(\binom{n-1}{m-1}\) if \(n \ge m\) and 0 otherwise.
• X: The balls are identical and the boxes are identical. (Empty boxes allowed.) Answer: Let \(p(n,m)\) be the number of partitions of \(n\) into at most \(m\) parts.
• XI: The balls are identical, the boxes are identical, and each box can hold at most one ball. Answer: 1 if \(n\le m\) and 0 otherwise.
• XII: The balls are identical, the boxes are identical, and each box must contain at least one ball. Answer: The number of partitions of \(n\) into exactly \(m\) parts (which is \(p(n,m)-p(n,m-1)\) with the convention \(p(n,0)=0\)).

The input will specify the case type along with the integers n and m. Solve the problem according to the given restrictions.

inputFormat

The first line contains a single integer \(T\) (\(T \ge 3\)), the number of test cases. Each of the following \(T\) lines contains a test case in the format:

case_type n m

Here, case_type is one of the Roman numeral strings from I to XII, and n and m are positive integers representing the number of balls and boxes respectively.

outputFormat

For each test case, output a single integer — the number of ways to distribute the balls into the boxes under the given restrictions, modulo \(998244353\).

sample

4
I 3 2
II 3 3
VII 3 2
IX 5 3

8
6
4
6