Problem O
Editing Explosion
Charles complains to Ada, “That Keats! So many spelling errors in this manuscript! How will I get them all fixed?”
Ada responds, “I’ve got a routine in the Engine that will help you. For a given word, it considers small errors and finds all the words that are close to that word, so they can be looked up in a lexicon of English. Here, hold my tea and watch this.”
Ada punches and threads cards furiously, then starts the Engine. Steam pours out of the boilers, and the Engine rumbles softly then more quickly, shaking the room, until finally an overloaded cam jams and the machine comes to a sudden halt.
“Hmm,” Ada muses, “I thought I had that worked out.”
The Levenshtein Distance between two strings is the smallest number of simple one-letter operations needed to change one string to the other. The operations are:
-
Adding a letter anywhere in the string.
-
Removing a letter from anywhere in the string.
-
Changing any letter in the string to any other letter.
You are given an input string on the alphabet ‘A’-‘Z’ and a Levenshtein distance. Output the count of distinct strings on the alphabet ‘A’-‘Z’, that are at exactly that Levenshtein distance from the input string. Since this number may be large, output it modulo the prime $998\, 244\, 353$.
Input
The single line of input contains a string $s$ ($1 \le |s| \le 10$, $s$ contains only upper-case letters) followed by a space, and then an integer $d$ ($0 \le d \le 10$), where $s$ is the string in question and $d$ is the Levenshtein distance of interest.
Output
Output a single integer, which is the count of distinct strings that are at Levenshtein distance $d$ from the input string $s$, in the alphabet ‘A’-‘Z’, modulo $998\, 244\, 353$. Note that the empty string is considered a valid result string.
| Sample Input 1 | Sample Output 1 |
|---|---|
ICPC 1 |
230 |
| Sample Input 2 | Sample Output 2 |
|---|---|
PROGRAMMER 10 |
110123966 |
