AT_scpc2026_div1_b Sushisushi Ruins

#### 表示言語 / / 考古学者のキム•ソックは，スシスシ遺跡で発見された碑文を研究している． 現在研究している遺跡の石板には長さ $ N $ の文字列 $ S $ が刻まれており，学者たちは長さ $ M $ の文字列 $ T $ が碑文の中に現れていると推定している． 長い時間が経つうちに，もともと刻まれていた文句の一部はまるごと消えてしまったという．あなたは次の方法で文字列を復元しようとしている． 1. $ T $ から長さ $ K $ の部分文字列を削除する．( $ 1 \leq K < M $ ) 2. 削除後の文字列が $ S $ の部分文字列として現れるなら，有効な復元方法であるという． 互いに異なる有効な復元方法の個数を求めよ．削除した部分文字列の長さ，削除した位置，削除後の文字列が $ S $ の部分文字列として現れる位置のうち，少なくとも $ 1 $ つが異なれば異なる復元方法である．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ S $ $ T $

互いに異なる有効な復元方法の個数を出力せよ．

### Constraints - $ 1 \leq N, M \leq 200\,000 $ - $ S $ と $ T $ はどちらも英小文字のみからなる - 入力される数値はすべて整数