Theo 有点过度自信了。他的 Spotify 密码刚刚泄露，他需要修改它。然而，他喜欢在输入密码时大声念出来，因此他修改了密码，使其恰好包含 $k$ 个不同的子串 shh 的出现实例。

如果字符串 $b$ 可以通过从字符串 $a$ 的开头删除若干个（可能是零个或全部）字符以及从结尾删除若干个（可能是零个或全部）字符来获得，则称 $b$ 是 $a$ 的子串。特别地，一个字符串是它自身的子串。如果从开头或结尾（或两者）删除的字符数量不同，则两个子串被视为不同的出现实例，即使最终得到的字符串内容相同。

给定原始密码，计算 Theo 最少需要修改多少个字符，才能使其恰好包含 $k$ 个不同的子串 shh 的出现实例。此外，计算在修改恰好这么多字符的前提下，Theo 可以构建出多少个不同的、且同样恰好包含 $k$ 个子串 shh 出现实例的密码。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 67$，$0 \le 3k \le n$）。

第二行包含一个长度为 $n$ 的由小写字母组成的字符串，表示 Theo 的原始密码。

输出格式

设 $c$ 为 Theo 最少需要修改的字符数。设 $w$ 为通过修改恰好 $c$ 个字符可以得到的、且恰好包含 $k$ 个子串 shh 出现实例的不同密码的数量。

输出两个整数：$c$，以及 $w$ 除以质数 $67$ 的余数。

样例

输入样例 1

10 2
eurovision

输出样例 1

5 4

说明 1

对于样例 1，可以证明至少需要修改 5 个字符。满足给定约束的四种可得到的密码分别为 shhovishhn、eshhvishhn、eushhishhn 和 eurshhshhn。

输入样例 2

8 1
sixseven

输出样例 2

2 2

输入样例 3

3 0
shh

输出样例 3

1 8

输入样例 4

2 0
no

输出样例 4

0 1

输入样例 5

10 0
wastedlove

输出样例 5

0 1

输入样例 6

18 6
countingsatellites

输出样例 6

18 1

输入样例 7

22 5
notanotherconstructive

输出样例 7

13 19

输入样例 8

14 3
honkaistarrail

输出样例 8

8 13