암호 찾기

오랜 기간 동안 세계 4대 문명이 최초의 문명으로 알려져 있었으나, 얼마 전 이를 뒤집는 고고학적 연구 결과가 발표되었습니다. 이번에 새로 발견된 문명인 ‘폴리매스 문명’은 기원전 9000년경부터 존재하였음이 확인되었습니다.

당신은 고고학자로, 폴리매스 문명을 연구하는 임무를 맡고 있습니다. 폴리매스 문명은 보안을 위해 특이한 형식의 비밀번호를 사용하였는데, 이에 대한 자세한 설명은 아래와 같습니다.

사람들은 비밀번호의 규칙과 관련된 두 개의 숫자들로 이루어진 문자열을 만들었습니다. 이 두 문자열 $A$와 $B$의 길이는 각각 $N$으로 같습니다. 이 중 $A$와 $B$ 모두의 부분 문자열이면서, 길이가 정확히 $K$인 것이 비밀번호가 됩니다.

비밀번호가 여러 개이거나 하나도 없을 수도 있는데, 이런 경우 $A$와 $B$가 기록이 잘못된 것입니다. 기록이 올바른지 판정하기 위해, 가능한 서로 다른 비밀번호의 수를 구하는 프로그램을 작성해 봅시다.

첫 줄에는 각 문자열의 길이 $N$과 뽑아낼 수의 자릿수 $K$가 주어집니다. 둘째 줄에는 문자열 $A$가 주어집니다. 셋째 줄에는 문자열 $B$가 주어집니다.

$A$와 $B$ 모두의 부분문자열이고 길이가 $K$인 서로 다른 문자열의 수를 출력합니다.

• $1 \le N \le 10^5$
• $1 \le K \le N$
• $|A| = |B| = N$
• $A$, $B$의 모든 문자는 1 이상 9 이하의 숫자입니다.