Multiset Maximum XOR

Given two integers n and m, count the number of multisets S of size n (i.e. a collection of n non‐negative integers, where the order does not matter and repetitions are allowed) with the following property:

If for any nonempty submultiset T ⊆ S we define its weight as the XOR-sum of its elements, i.e.,

$$Q_T = a_1 \oplus a_2 \oplus \dots \oplus a_{|T|}, $$

then it holds that $$\max_{\emptyset\neq T\subseteq S} Q_T = m.$$

Notes:

• Every element of the multiset is a non-negative integer.
• The size of the multiset is the total number of elements (counting repetitions).
• Even if the same number appears more than once, the multiset is considered without order. For example, \(\{1,2,3\}\) and \(\{3,2,1\}\) are considered the same multiset.
• You are given that the answer is finite. (In fact, any element greater than m would immediately yield a single‐element subset with XOR greater than m.)

It can be shown that the answer only depends on the distinct numbers present in S. In particular, if we denote by F the set of distinct values in S, then the set of all XOR values attainable from nonempty subsets of S is the same as that from F (since each element appears at least once and repeated occurrences allow you to choose the parity arbitrarily). Hence, the condition is equivalent to saying that the maximum XOR over nonempty subsets of F is exactly m.

If we denote by \(F'\) a nonempty subset of \(\{0, 1, 2, \dots, m\}\) (note that any element \(x > m\) cannot appear in S because its singleton subset would have weight \(x > m\)), then in any multiset S whose set of distinct elements is exactly \(F'\), the condition holds if and only if $$\max_{\emptyset \neq T \subseteq F'} \;\text{XOR}(T) = m. $$

For any fixed nonempty (F'), the number of multisets S of size n with distinct set (F') is equal to the number of solutions of

$$f(x)=\{f(0), f(1),\dots,f(m)\},\quad \sum_{x=0}^{m} f(x)=n,\quad f(x)\ge 0 \;\text{and}\; f(x)>0\; \text{if}\; x\in F' \text{ and } f(x)=0 \;\text{if}\; x\notin F'. $$

This number is (C(n-1, |F'|-1)) (a stars‐and‐bars result). Therefore, the final answer is the sum of (C(n-1, |F'|-1)) over all nonempty (F'\subseteq {0,1,\dots,m}) such that the maximum XOR over nonempty subsets of (F') is exactly (m).

Since the answer may be large, output it modulo 998244353.

inputFormat

The input consists of a single line with two integers n and m (with n ≥ 1 and m ≥ 0). It is guaranteed that based on the value of m, any element x in a valid multiset S must satisfy 0 ≤ x ≤ m.

outputFormat

Output a single integer, the number of multisets S of size n satisfying the property that the maximum XOR (over all nonempty subsets) is exactly m, taken modulo 998244353.

sample

1 0

1