Code Lock

有一个圆形密码锁分为 $k$ 段（从 $1$ 开始编号）。箭头始终指向其中一段。每段都标记有前 $k$ 个小写字母中的一个。没有两段用同一个字母。密码是一个长度为 $n$ 的仅由小写字母前 $k$ 组成的字符串。最初，锁的箭头指向编号 $1$，输入屏幕为空。每次你可以做以下操作之一。 - 将箭头顺时针旋转一段。 - 将箭头逆时针旋转一段。 - 输入当前箭头指向段的字母。 你可以将 $k$ 个字母按任意顺序分配到密码锁。问输入密码的最小操作次数和可以使得操作次数最小的分配字母的方案数。 $2\le k\le 16,2\le n\le 10^5$

Lara has a safe that is locked with a circle-shaped code lock that consists of a rotating arrow, a static circumference around the arrow, an input screen, and an input button. The circumference of the lock is split into $ k $ equal sections numbered from $ 1 $ to $ k $ in clockwise order. Arrow always points to one of the sections. Each section is marked with one of the first $ k $ letters of the English alphabet. No two sections are marked with the same letter. Due to the lock limitations, the safe's password is a string of length $ n $ that consists of first $ k $ letters of the English alphabet only. Lara enters the password by rotating the lock's arrow and pressing the input button. Initially, the lock's arrow points to section $ 1 $ and the input screen is empty. In one second she can do one of the following actions. - Rotate the arrow one section clockwise. If the arrow was pointing at section $ x < k $ it will now point at section $ x + 1 $ . If the arrow was pointing at section $ k $ it will now point at section $ 1 $ . - Rotate the arrow one section counter-clockwise. If the arrow was pointing at section $ x > 1 $ it will now point at section $ x - 1 $ . If the arrow was pointing at section $ 1 $ it will now point at section $ k $ . - Press the input button. The letter marked on the section that the arrow points to will be added to the content of the input screen. As soon as the content of the input screen matches the password, the safe will open. Lara always enters her password in the minimum possible time.Lara has recently found out that the safe can be re-programmed. She can take the first $ k $ letters of the English alphabet and assign them to the sectors in any order she likes. Now she wants to re-arrange the letters in a way that will minimize the number of seconds it takes her to input the password. Compute this minimum number of seconds and the number of ways to assign letters, for which this minimum number of seconds is achieved. Two ways to assign letters to sectors are considered to be distinct if there exists at least one sector $ i $ that is assigned different letters.

The first line of the input contains two integers $ k $ and $ n $ ( $ 2 \leq k \leq 16 $ , $ 2 \leq n \leq 100\,000 $ ) — the number of sectors on the lock's circumference and the length of Lara's password, respectively. The second line of the input contains a string of length $ n $ that consists of the first $ k $ lowercase letters of the English alphabet only. This string is the password.

On the first line print minimum possible number of seconds it can take Lara to enter the password and open the safe if she assigns letters to sectors optimally. On the second line print the number of ways to assign letters optimally.

3 10
abcabcabca

19
2

4 20
bcbcbcbcadadadadcbda

40
2

4 6
adcbda

12
4

The initial states of optimal arrangements for the first example are shown in the figure below. The initial states of optimal arrangements for the second example are shown in the figure below. The initial states of optimal arrangements for the third example are shown in the figure below.