[Solution] Multiset of Strings solution codeforces

Multiset of Strings solution codeforces – You are given three integers 𝑛n𝑘k and 𝑓f.

Consider all binary strings (i. e. all strings consisting of characters 00 and/or 11) of length from 11 to 𝑛n. For every such string 𝑠s, you need to choose an integer 𝑐𝑠cs from 00 to 𝑘k.

Table of Contents

[Solution] Multiset of Strings solution codeforces

A multiset of binary strings of length exactly 𝑛n is considered beautiful if for every binary string 𝑠s with length from 11 to 𝑛n, the number of strings in the multiset such that 𝑠s is their prefix is not exceeding 𝑐𝑠cs.

For example, let 𝑛=2n=2𝑐0=3c0=3𝑐00=1c00=1𝑐01=2c01=2𝑐1=1c1=1𝑐10=2c10=2, and 𝑐11=3c11=3. The multiset of strings {11,01,00,01}{11,01,00,01} is beautiful, since:

  • for the string 00, there are 33 strings in the multiset such that 00 is their prefix, and 3𝑓03≤f0;
  • for the string 0000, there is one string in the multiset such that 0000 is its prefix, and 1𝑐001≤c00;
  • for the string 0101, there are 22 strings in the multiset such that 0101 is their prefix, and 2𝑐012≤c01;
  • for the string 11, there is one string in the multiset such that 11 is its prefix, and 1𝑐11≤c1;
  • for the string 1010, there are 00 strings in the multiset such that 1010 is their prefix, and 0𝑐100≤c10;
  • for the string 1111, there is one string in the multiset such that 1111 is its prefix, and 1𝑐111≤c11.

Now, for the problem itself. You have to calculate the number of ways to choose the integer 𝑐𝑠cs for every binary string 𝑠s of length from 11 to 𝑛n in such a way that the maximum possible size of a beautiful multiset is exactly 𝑓f.

Input

The only line of input contains three integers 𝑛n𝑘k and 𝑓f (1𝑛151≤n≤151𝑘,𝑓21051≤k,f≤2⋅105).

[Solution] Multiset of Strings solution codeforces

Print one integer — the number of ways to choose the integer 𝑐𝑠cs for every binary string 𝑠s of length from 11 to 𝑛n in such a way that the maximum possible size of a beautiful multiset is exactly 𝑓f. Since it can be huge, print it modulo 998244353998244353.

Examples
input

Copy
1 42 2
output

Copy
3
input

Copy
2 37 13
output

Copy
36871576

[Solution] Multiset of Strings solution codeforces

input

Copy
4 1252 325
output

Copy
861735572
input

Copy
6 153 23699
output

Copy
0
input

Copy
15 200000 198756
output

Copy
612404746
Note

In the first example, the three ways to choose the integers 𝑐𝑠cs are:

  • 𝑐0=0c0=0𝑐1=2c1=2, then the maximum beautiful multiset is {1,1}{1,1};
  • 𝑐0=1c0=1𝑐1=1c1=1, then the maximum beautiful multiset is {0,1}{0,1};
  • 𝑐0=2c0=2𝑐1=0c1=0, then the maximum beautiful multiset is {0,0}{0,0}.

 

For Solution

Click Here

Leave a Comment