CF1804H.Code Lock

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 \lt 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 \gt 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.

拉拉有一个保险箱，其密码锁为圆形，由一个可旋转的指针、围绕指针的固定圆周、一个输入屏幕和一个输入按钮组成。

该锁的圆周被均分为 $k$ 个扇区，按顺时针方向编号为 $1$ 至 $k$。指针始终指向其中一个扇区。每个扇区标有一个英文字母，且恰好取自英文字母表的前 $k$ 个字母（即 a, b, ..., 第 $k$ 个字母）。任意两个扇区所标的字母互不相同。

受锁具限制，保险箱的密码是一个长度为 $n$ 的字符串，且仅由英文字母表的前 $k$ 个字母构成。拉拉通过旋转指针并按下输入按钮来输入密码。初始状态下，指针指向扇区 $1$，输入屏幕为空。每秒钟她可以执行以下操作之一：

• 将指针顺时针旋转一格：若指针原指向扇区 $x < k$，则现指向扇区 $x + 1$；若原指向扇区 $k$，则现指向扇区 $1$。
• 将指针逆时针旋转一格：若指针原指向扇区 $x > 1$，则现指向扇区 $x - 1$；若原指向扇区 $1$，则现指向扇区 $k$。
• 按下输入按钮：将指针当前所指扇区上标记的字母添加到输入屏幕内容末尾。

一旦输入屏幕的内容与密码完全一致，保险箱即开启。拉拉总是以最短可能时间输入她的密码。

最近，拉拉发现该保险箱可重新编程。她可以取英文字母表的前 $k$ 个字母，并以任意顺序将它们分配给各个扇区。现在，她希望以某种方式重新排列这些字母，使得输入密码所需的时间（秒数）最小化。请计算该最小时间（秒数），以及能实现该最小时间的不同字母分配方案数。

若存在至少一个扇区 $i$，在两种分配方案中被赋予了不同的字母，则认为这两种字母分配方案互不相同。

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.

输入的第一行包含两个整数 $k$ 和 $n$（$2 \leq k \leq 16$，$2 \leq n \leq 100\,000$），分别表示密码锁圆周上的扇区数量和 Lara 密码的长度。

输入的第二行包含一个长度为 $n$ 的字符串，该字符串仅由英语字母表的前 $k$ 个小写字母组成。该字符串即为密码。

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.

第一行输出 Lara 在最优地将字母分配给扇区的情况下，输入密码并打开保险箱所需的最少秒数。

第二行输出最优分配字母的方案数。

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.

第一个示例的最优排列的初始状态如下图所示。

第二个示例的最优排列的初始状态如下图所示。

第三个示例的最优排列的初始状态如下图所示。