만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

쌍둥이 친구

시간 제한2초메모리 제한1024 MB

요약
A의 순열 A'와 B에서 M-N개를 지워 만든 길이 N의 B' 쌍 중, 각 위치의 B' 글자가 A' 글자이거나 그 다음 알파벳인 경우의 수를 998244353으로 나눈 나머지로 구합니다.
난이도

보통10점 중 6점

유형
조합론, 동적 계획법, 누적 합
정답자
아직 제출이 없습니다

문제

쌍둥이 친구 두 명을 만났다. 언니의 이름은 AA이고 NN개의 문자로 이루어져 있다. 동생의 이름은 BB이고 MM개의 문자로 이루어져 있다. N≤MN \le M이다.

두 사람에게 별명을 하나씩 붙이려고 한다. 언니의 별명 A′A'는 AA의 임의의 순열로 정한다. 동생의 별명 B′B'는 BB의 임의의 순열에서 정확히 M−NM - N개의 문자를 지워서 만든다.

두 별명은 다음 조건을 만족해야 한다. 1≤i≤N1 \le i \le N인 모든 ii에 대해 Bi′B'_i는 Ai′A'_i이거나, Ai′A'_i의 알파벳 다음 글자다. 다음 글자가 없으면 후자는 해당하지 않는다.

조건을 만족하는 서로 다른 별명 쌍 (A′,B′)(A', B')의 개수를 구한다. 두 쌍 중 별명 하나라도 다르면 서로 다른 쌍으로 본다. 개수가 클 수 있으므로 998244353998244353으로 나눈 나머지를 구한다.

입력

첫째 줄에 정수 NN과 MM (1≤N≤M≤2000001 \le N \le M \le 200000)이 주어진다.

둘째 줄에 길이 NN인 문자열 AA가 주어진다.

셋째 줄에 길이 MM인 문자열 BB가 주어진다.

모든 문자열은 대문자 알파벳으로만 이루어진다.

출력

조건을 만족하는 쌍 (A′,B′)(A', B')의 개수를 998244353998244353으로 나눈 나머지를 출력한다.

예제4

  1. 예제 1

    입력
    3 4
    AMA
    ANAB
    
    예상 출력
    9
    
  2. 예제 2

    입력
    5 8
    BINUS
    BINANUSA
    
    예상 출력
    120
    
  3. 예제 3

    입력
    15 30
    BINUSUNIVERSITY
    BINANUSANTARAUNIVERSITYJAKARTA
    
    예상 출력
    151362308
    
  4. 예제 4

    입력
    4 4
    UDIN
    ASEP
    
    예상 출력
    0