У Лары есть сейф, который запирается кодовым замком в форме круга, состоящим из вращающейся стрелки, статической окружности вокруг стрелки, экрана ввода и кнопки ввода.

Окружность замка разбита на $$$k$$$ равных секторов, пронумерованных от $$$1$$$ до $$$k$$$ по часовой стрелке, вращающаяся стрелка всегда указывает на один из этих секторов. Каждому сектору соответствует одна из первых $$$k$$$ букв английского алфавита, причём никаким двум секторам не соответствует одна и та же буква.

Из-за ограничений устройства сейфа пароль от него представляет собой строку длины $$$n$$$, состоящую из только первых $$$k$$$ букв английского алфавита. Лара вводит пароль поворачивая стрелку замка и нажимая кнопку ввода. Изначально стрелка замка указывает на секцию $$$1$$$, а экран ввода пуст, далее за одну секунду Лара может выполнить одно из следующих действий.

• Повернуть стрелку на один сектор по часовой стрелке. Если стрелка указывала на сектор $$$x < k$$$, то теперь она будет указывать на сектор $$$x + 1$$$. Если же стрелка указывала на сектор $$$k$$$, то теперь она будет указывать на сектор $$$1$$$.
• Повернуть стрелку на один сектор против часовой стрелки. Если стрелка указывала на сектор $$$x > 1$$$, то теперь она будет указывать на сектор $$$x - 1$$$. Если стрелка указывала на сектор $$$1$$$, то теперь она будет указывать на сектор $$$k$$$.
• Нажать на кнопку ввода. В конец содержимого экрана ввода добавляется буква, соответствующая сектору, на который указывает сейчас стрелка.

Как только содержимое экрана ввода совпадёт с паролем, сейф откроется. Лара всегда действует таким образом, чтобы вводить свой пароль за минимально возможное время.

Недавно Лара узнала, что сейф можно перепрограммировать. Она может взять первые $$$k$$$ букв английского алфавита и переназначить их секторам в произвольном порядке. Теперь она хочет переназначить буквы таким образом, чтобы свести к минимуму количество секунд, необходимых ей для ввода пароля. Вычислите это минимально возможное количество секунд, а также вычислите количество способов расставить буквы по секторам, для которых это минимальное количество секунд будет достигаться.

Два способа назначения букв секторам считаются различными, если существует хотя бы один сектор $$$i$$$, которому в этих способах назначены разные буквы.