Background

Problem Description

Given $r, m, s$, ask how many pairs of positive integers $(fi, sh)$ satisfy:

• $0 \le fi \le sh \le r$.

• $\operatorname{popcount}(fi \oplus sh) = m$.

• $\operatorname{popcount}(fi + sh) = s$.

Here, $\operatorname{popcount}(x)$ denotes the number of $1$'s in the binary representation of $x$, and $\oplus$ denotes the XOR operation.

For convenience, $r$ is given in binary.

It is guaranteed that none of the given numbers has leading $0$.

Output the answer modulo $998244353$.

Input Format

One line with three integers $r, m, s$.

Output Format

One line with one integer, the answer modulo $998244353$.

111 1 2 

6

Hint

Sample Explanation:

All numbers below are in decimal.

When $r = 7$, there are six pairs: $(1,5), (2,3), (3,7), (4,5), (4,6), (5,7)$.

Constraints:

Let $n$ be the length of the given $r$.

For $100\%$ of the data, $1 \le n, m, s \le 200$.

This problem uses bundled testdata.

• Subtask 1 (15 pts): $n \le 12$.
• Subtask 2 (25 pts): $m, s \le 30$.
• Subtask 3 (25 pts): $r = 2^n - 1$.
• Subtask 4 (35 pts): no special constraints.

Translated by ChatGPT 5