Problem Description

Theo needs to change his leaked password. Because he likes to say his password aloud while typing it, he wants the new password to contain exactly $k$ occurrences of the substring shh.

A substring is a contiguous segment of a string. Two occurrences are different if they begin or end at different positions, even if their contents are identical.

Given Theo's original password, find the minimum number of characters he must change to obtain exactly $k$ occurrences of shh. Also count the distinct passwords obtainable by changing exactly that many characters and containing exactly $k$ occurrences.

Input Format

The first line contains two integers $n$ and $k$ ($1\le n\le67$ and $0\le3k\le n$).

The second line contains Theo's original password, a string of $n$ lowercase English letters.

Output Format

Let $c$ be the minimum number of changed characters and $w$ the number of valid passwords at that distance. Output $c$ and $w\bmod67$.

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

Hint

In the first sample, at least five characters must be changed. The four valid passwords are shhovishhn, eshhvishhn, eushhishhn, and eurshhshhn.