题目描述

Theo 有些过于自信。他的 Spotify 密码刚刚泄露，需要换一个新密码。然而，他喜欢一边输入密码一边把它大声念出来，因此他决定把密码改成恰好含有 $k$ 个不同的子串 shh 的形式。

如果字符串 $b$ 可以通过从字符串 $a$ 的开头删除若干个字符（可以为零个或全部），并从末尾删除若干个字符（同样可以为零个或全部）得到，那么 $b$ 是 $a$ 的子串。特别地，一个字符串也是它自身的子串。

如果为了得到两个子串而从开头或末尾删除的字符数量至少有一项不同，就认为它们是两个不同的子串实例；即使最终得到的字符串内容相同也是如此。

给定原密码，求 Theo 至少需要修改多少个字符，才能使密码中恰好有 $k$ 个不同的 shh 子串实例。此外，求恰好修改这么多个字符后，能够得到多少个恰含 $k$ 个 shh 子串实例的不同密码。

输入格式

第一行包含两个整数 $n,k$，满足 $1\le n\le67$ 且 $0\le3k\le n$。

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

输出格式

令 $c$ 为 Theo 至少需要修改的字符数，$w$ 为恰好修改 $c$ 个字符后能得到的、恰含 $k$ 个 shh 子串实例的不同密码数量。

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

10 2
eurovision

5 4

8 1
sixseven

2 2

3 0
shh

1 8

2 0
no

0 1

10 0
wastedlove

0 1

18 6
countingsatellites

18 1

22 5
notanotherconstructive

13 19

14 3
honkaistarrail

8 13

提示

对于样例 1，可以证明至少需要修改 $5$ 个字符。满足条件的四个密码分别是 shhovishhn、eshhvishhn、eushhishhn 和 eurshhshhn。