题目描述

文件压缩和解压是指对一个或多个文件进行压缩和解压缩操作，以便于传输、存储和备份。本题中我们只考虑对字符串进行展开和简写。

现在我们介绍两种字符串的简写方式：

• 方式 1：对于一个字符串，将字符串中连续且由相同字符组成的子串替换为子串中含有字符的个数和该字符。例如 xxx 就用 3x 来代替，如果字符没有重复，就原样输出，例如 TxT 简写之后仍然是 TxT。
• 方式 2：对于一个字符串，将字符串首尾之间的片段替换为首尾字符之间的字符个数。例如 shenzejiaoyu 就用 x10e 来代替，保证方式 2 下操作的字符串的长度都大于 2。

对于方式 1 简写之后的字符串进行展开的方法就是简写的逆过程，例如 5T 展开之后就是 TTTTT。

为了“简化”本题，我们规定只有长度不小于 k 的字符串才能使用方式 2 进行简写。

现在给定你一个由方式 1 简写之后的字符串 s，你需要先对该字符串进行展开，假设展开之后的字符串为 s′。然后再给定你两个字符 b 和 e，请你计算字符串 s′ 中有多少个由 b 开头且以 e 结尾的子串可以使用方式 2 简写，保证字符 b 和 e 一定出自字符串 s′。

输入格式

第一行，包含一个字符串s

第二行，包含一个整数k和两个字符b 和e。

对于 60% 数据保证：$3\le k\le |s$'$|\le 5\times 10^{3}$。

对于 100% 数据保证：$3\le k\le |s$'$|\le 5\times 10^{5}$，字符串 s′ 表示字符串 s 展开之后的结果，s′ 只包含大小字母。

输出格式

一行，包含一个整数，表示结果。

样例输入

3x2txt
4 x t

样例输出

6

提示

将样例字符串展开后得到 xxxttxt。以 x 开头、以 t 结尾且长度不小于 $k=4$ 的子串共有 $6$ 个。

对于 60% 数据保证：$3\le k\le |s$'$|\le 5\times 10^{3}$。

对于 100% 数据保证：$3\le k\le |s$'$|\le 5\times 10^{5}$，字符串 s′ 表示字符串 s 展开之后的结果，s′ 只包含大小字母。

2a3b
5 a b

1

10a
5 a a

21

5b3c2d
4 a b

0