Count Integer Pairs with Bitwise Constraints

Given a binary string (r) (with no leading zeros) and two integers (m) and (s), count the number of pairs of integers ((fi, sh)) satisfying:

\begin{enumerate} \item (0 \le fi \le sh \le r), where (r) is interpreted as its decimal value given in binary form. \item (\operatorname{popcount}(fi \oplus sh) = m), where (\oplus) denotes the bitwise XOR operation and (\operatorname{popcount}(x)) is the number of ones in the binary representation of (x). \item (\operatorname{popcount}(fi + sh) = s). \end{enumerate}

Output the answer modulo (998244353).

inputFormat

The input consists of a single line containing the binary string (r) and two integers (m) and (s) separated by spaces. It is guaranteed that (r) does not contain any leading zeros.

outputFormat

Output a single integer, which is the number of valid pairs ((fi, sh)) modulo (998244353).

sample

10 1 1

4