쌍둥이 친구
시간 제한2초메모리 제한1024 MB
A의 순열 A'와 B에서 M-N개를 지워 만든 길이 N의 B' 쌍 중, 각 위치의 B' 글자가 A' 글자이거나 그 다음 알파벳인 경우의 수를 998244353으로 나눈 나머지로 구합니다.
문제
쌍둥이 친구 두 명을 만났다. 언니의 이름은 이고 개의 문자로 이루어져 있다. 동생의 이름은 이고 개의 문자로 이루어져 있다. 이다.
두 사람에게 별명을 하나씩 붙이려고 한다. 언니의 별명 는 의 임의의 순열로 정한다. 동생의 별명 는 의 임의의 순열에서 정확히 개의 문자를 지워서 만든다.
두 별명은 다음 조건을 만족해야 한다. 인 모든 에 대해 는 이거나, 의 알파벳 다음 글자다. 다음 글자가 없으면 후자는 해당하지 않는다.
조건을 만족하는 서로 다른 별명 쌍 의 개수를 구한다. 두 쌍 중 별명 하나라도 다르면 서로 다른 쌍으로 본다. 개수가 클 수 있으므로 으로 나눈 나머지를 구한다.
입력
첫째 줄에 정수 과 ()이 주어진다.
둘째 줄에 길이 인 문자열 가 주어진다.
셋째 줄에 길이 인 문자열 가 주어진다.
모든 문자열은 대문자 알파벳으로만 이루어진다.
출력
조건을 만족하는 쌍 의 개수를 으로 나눈 나머지를 출력한다.