题目描述Description

存在两个长度分别为 \(n\) 和 \(m\) 的字符串 \(S\) 和 \(T\)。

小A为了检验 \(S\) 和 \(T\) 是否能合成室温超导材料，对 \(S\) 的任意非空子串 \(S[i...j]\)，在 \(T\) 中选取任意长度不超过 \(n-j+1\) 的后缀与其拼接，得到测试样品，再进行下一步的超导测试。即测试样品的一种合成方式为 \(S[i...j] + T[k...m]\)，满足\(1 \leq i \leq j \leq n，1 \leq k \leq m\)，且 \(m-k \leq n-j\)。

为了能尽快完成实验，小A想知道在所有的合成方式中，最终能得到的不同测试样品的数量。

输入格式Input

第一行两个整数 \(n\) 和 \(m\)，分别代表 \(S\) 和 \(T\) 的长度\((1\leq m\leq n\leq 500000)\)。

第二、第三行为两个字符串，代表 \(S\) 和 \(T\)。

\(S\) 和 \(T\) 只包含小写字母

输出格式Output

一个整数，表示不同测试样品的数量。

提示Hint

样例一：

\(S[1,1]\) 可以合成 abc, ac

\(S[2,2]\) 可以合成 abc, ac

\(S[3,3]\) 可以合成 bc

\(S[1,2]\) 可以合成 aabc, aac

\(S[2,3]\) 可以合成 abc

\(S[1,3]\) 可以合成 aabc

一共可以得到 ac, bc, abc, aac, aabc 5种不同的测试样品

来源Source