Key Generation

Time limit1sMemory limit512 MB

Summary

Count the nonnegative integers up to N whose binary form has exactly K ones, given N as a hex string of up to 250 digits, modulo 998244353.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Bit manipulation, Math
Solved: No attempts yet

Problem

In the cryptographic system <>, a key can be any nonnegative integer whose binary representation contains exactly $K$ ones and which does not exceed a given positive integer $N$ .

Given $N$ and $K$ , compute how many distinct keys exist. Since the answer can be very large, output its remainder modulo the prime $998\,244\,353$ .

Input

The first line contains a single integer $N$ written in hexadecimal notation without leading zeros ( $1 \le N < 16^{250}$ ). Digits greater than 9 are denoted by uppercase Latin letters from 'A' to 'F'.

The second line contains a single integer $K$ , the number of bits in the key that equal one ( $0 \le K \le 1\,000$ ).

Output

Print a single number: the remainder when the number of distinct keys that exist for the given $N$ and $K$ is divided by the prime $998\,244\,353$ .

Examples2

Example 1
Input
```
1F
2
```
Expected output
```
10
```
Example 2
Input
```
31
3
```
Expected output
```
17
```