今天是 Jaime 的生日。为了庆祝，他的朋友们订购了一个用蛋黄果（eggfruit）和柿子（persimmon）装饰的蛋糕。蛋糕送达时，令他们惊讶的是，面包店并没有使用等量的蛋黄果和柿子，而是将这些水果随机分布在蛋糕的边缘。

Jaime 每天都吃柿子，所以他渴望在生日那天尝尝蛋黄果。然而，因为他不想吃得太多，他的蛋糕切片上最多只能装饰 $S$ 个水果。由于 Jaime 不喜欢水果被切成碎片，每个水果要么完整地包含在他的切片中，要么留在蛋糕的其余部分。问题在于，水果的分布如此混乱，他的朋友们很难为他切出一块合适的蛋糕。

Jaime 正准备抱怨朋友们切蛋糕花的时间太长了，但为了有理有据，他需要知道有多少种不同的切片，满足：至少包含一个蛋黄果，且最多包含 $S$ 个水果。切片仅根据其包含的水果集合来定义。由于 Jaime 非常注重细节，他能够区分任何两个水果，即使它们是同一种类型。因此，当两块切片包含的水果集合不完全相同时，它们就被认为是不同的。下图展示了一个可能的蛋糕，以及从中可以切出的最多包含 $S = 2$ 个水果的六种不同切片。

输入格式

第一行包含一个环形字符串 $B$（$3 \le |B| \le 10^5$），描述蛋糕的边缘。$B$ 中的每个字符要么是大写字母 "E"，要么是大写字母 "P"，分别表示蛋糕边缘该位置是一个蛋黄果或一个柿子。

第二行包含一个整数 $S$（$1 \le S < |B|$），表示一块切片最多可以包含的水果数量。

输出格式

输出一行，包含一个整数，表示最多包含 $S$ 个水果且至少包含一个蛋黄果的不同切片数量。

样例

输入 1

PEPEP
2

输出 1

6

输入 2

EPE
1

输出 2

2

输入 3

PPPP
1

输出 3

0

输入 4

EPEP
2

输出 4

6