편집 거리 세기

Charles가 Ada에게 불평한다. "이 Keats라는 작자! 원고에 맞춤법 오류가 이렇게 많다니! 이걸 다 어떻게 고치지?"

Ada가 답한다. "Engine에 도움이 될 만한 루틴이 있어요. 어떤 단어가 주어지면 작은 오류들을 고려해서 그 단어에 가까운 단어를 모두 찾아 주니, 영어 사전에서 찾아볼 수 있어요. 여기, 제 차 좀 들고 이걸 보세요."

Ada가 카드를 빠르게 구멍 뚫고 실에 꿰더니, Engine을 가동한다. 보일러에서 증기가 뿜어져 나오고, Engine이 조용히 웅웅거리다 점점 빨라져 방을 흔들더니, 마침내 과부하가 걸린 캠이 뻑 하고 멈추면서 기계가 갑자기 서 버린다.

"흠," Ada가 중얼거린다. "난 그거 해결한 줄 알았는데."

두 문자열의 Levenshtein 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 가장 적은 수의 한 글자 연산이다. 연산은 다음과 같다.

• 문자열 어디에든 글자 하나를 추가한다.
• 문자열 어디에서든 글자 하나를 제거한다.
• 문자열의 어떤 글자든 다른 글자로 바꾼다.

알파벳 ‘A’-‘Z’로 이루어진 입력 문자열과 Levenshtein 거리가 주어진다. 입력 문자열과의 Levenshtein 거리가 정확히 그 값인, 알파벳 ‘A’-‘Z’로 이루어진 서로 다른 문자열의 개수를 출력하라. 이 수는 클 수 있으므로 소수 998,244,353으로 나눈 나머지를 출력하라.

입력의 한 줄에는 문자열 s (1 ≤ |s| ≤ 10, s는 대문자만 포함)와 공백 하나, 그다음 정수 d (0 ≤ d ≤ 10)가 주어진다. s는 문제의 문자열이고 d는 관심 있는 Levenshtein 거리이다.

입력 문자열 s와의 Levenshtein 거리가 d인, 알파벳 ‘A’-‘Z’로 이루어진 서로 다른 문자열의 개수를 998,244,353으로 나눈 나머지를 한 정수로 출력하라. 빈 문자열도 유효한 결과 문자열로 간주한다.