题目描述

徐老师有一根彩带，这根彩带上一共有 $26$ 种不同的颜色，并且彩带均匀的分割成了 $n$ 块长度为 $1$ 的部分，每一块都有一种颜色，从左往右数第 $i$ 块的颜色用 $a_i$ 来表示

现在徐老师希望能够得到一根完美的彩带，这根彩带的长度为 $m$ ，并且颜色依次为 $b_i$

但是徐老师很懒，他懒得专门切那么多刀去得到这根完美的彩带，于是他决定——只切最多两刀！

也就是徐老师可以选择以下四种方案之一：

1. 在某个位置切一刀，丢掉左边的部分，保留右边的部分
2. 在某个位置切一刀，丢掉右边的部分，保留左边的部分
3. 选择两个位置分别切一刀，然后保留中间的部分
4. 一刀都不切

但是这样切出来的彩带不一定是完美的彩带，但是没有关系

徐老师认为只要切出来的彩带中依次包含着 $b_i$（可以不连续）那么这根彩带就是次完美的彩带，也能接受！

例如 $b=abcd$，那么对于 $s=abccd,adbdcd$ 都是满足的

现在徐老师想知道，他一共有多少种切法能够得到次完美或者完美的彩带？

输入格式

输入第一行包含两个整数 $n,m$，含义如题

输入第二行包含一个字符串 $a$，依次表示原彩带的颜色，其中每种颜色用一个小写字母表示

输入第三行包含一个字符串 $b$，依次表示完美彩带的颜色，其中每种颜色用一个小写字母表示

输出格式

输出一个整数，表示徐老师一共有多少种不同的切彩带方案

其中，如果是切两刀的方案，两刀不分先后，即先切 $i$ 再切 $j$ 和先切 $j$ 再切 $i$ 属于同一种方案

数据范围

数据点编号	$n$	$m$
$1$	$1 \leq n \leq 10$	$1 \leq m \leq 10$
$2$	$1 \leq n \leq 100$	$1 \leq m \leq 100$
$3 \sim 6$	$1 \leq n \leq 1000$
$7 \sim 8$	$1 \leq n \leq 10^5$
$9 \sim 10$	$1 \leq n \leq 3*10^5$

样例输入1

8 3
abczdefg
zfg

样例输出1

4

样例解释1

1. 一刀都不切
2. 在 ab 之间切一刀，丢掉左边部分
3. 在 bc 之间切一刀，丢掉左边部分
4. 在 cz 之间切一刀，丢掉左边部分

样例输入2

5 2
abcdd
cd

样例输出2

6

样例解释2

1. 一刀都不切
2. 在 ab 之间切一刀，丢掉左边部分
3. 在 bc 之间切一刀，丢掉左边部分
4. 在 dd 之间切一刀，丢掉右边部分
5. 在 ab 和 dd 之间切一刀，保留中间部分
6. 在 bc 和 dd 之间切一刀，保留中间部分