409056: GYM103428 B Subset

Given a set $$$S$$$ of first $$$N+1$$$ non-negative integers i.e. $$$S = \{0, 1, 2, ..., N\}$$$. Find number of ways of choosing a $$$K$$$ size subset of $$$S$$$ with the property that the XOR-sum of all chosen integers has exactly $$$B$$$ set bits in its binary representation (i.e. the bits that are equal to $$$1$$$). Since the answer can be large, output it modulo $$$998244353$$$.

The only line of input contains three space-separated integers $$$N\ (1\le N\le10^9)$$$, $$$K\ (1\le K\le5000)$$$ and $$$B\ (0\le B\le30)$$$.

Output a single line containing the answer.

2 2 0

0

2 2 1

2

2 2 2

1

XOR-sum of $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ will be $$$a_1\ xor\ a_2\ xor\ \cdots\ a_n$$$. By xor, we mean bit-wise xor.