AT_scpc2026_div1_b Sushisushi Ruins

#### 表示言語 / / Archaeologist seokgukim is studying an inscription discovered at the Sushisushi ruins. The stone tablet currently being studied has a string $ S $ of length $ N $ engraved on it, and scholars believe that a string $ T $ of length $ M $ appears in the inscription. Over a long period of time, some part of the originally engraved text is said to have disappeared entirely. You want to restore the string using the following method. 1. Delete a substring of length $ K $ from $ T $ . ( $ 1 \leq K < M $ ) 2. If the string after deletion appears as a substring of $ S $ , this is called a valid restoration method. Find the number of distinct valid restoration methods. Two valid restoration methods are considered different if at least one of the following differs: the length of the deleted substring, the position of the deleted substring, or the position where the string after deletion appears as a substring of $ S $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ S $ $ T $

Output the number of distinct valid restoration methods.

### Constraints - $ 1 \leq N, M \leq 200\,000 $ - Both $ S $ and $ T $ consist only of lowercase English letters. - All given numbers are integers.