18478번 - K-pop Strings 다국어

A substring s[l..r] is a tandem repeat if r − l + 1 is even and s[l . . . (l+r−1)/2] = s[(l+r+1)/2. . . r].

Recently Gennady came up with a method to calculate the number of tandem repeats in a string using suffix structures, and now he came up with a new type of strings based on tandem repeats. Gennady thinks that string s of length n is a K-pop string if there are no tandem repeats of length ≥ n − k.

Help him find the number of K-pop strings consisting only of the characters ‘1’, ‘2’, . . . , ‘9’, ‘a’, ‘b’, . . . , ‘z’, modulo 998 244 353.

The first line of input contains two integers n and k: the required length of string and the parameter (1 ≤ n ≤ 100, 0 ≤ k ≤ 16).

Output one integer: the number of K-pop strings of length n for the given k, consisting only of nonzero digits and lowercase alphabetic characters, modulo 998 244 353.

The answer for the first example is 35 because all strings of length 1 are possible: “1”, “2”, . . . , “9”, “a”, “b”, . . . , “z”.

The answer for the second example is 35⁴ − 35².