У Лары есть сейф, который запирается кодовым замком в форме круга, состоящим из вращающейся стрелки, статической окружности вокруг стрелки, экрана ввода и кнопки ввода.
Окружность замка разбита на \(k\) равных секторов, пронумерованных от \(1\) до \(k\) по часовой стрелке, вращающаяся стрелка всегда указывает на один из этих секторов. Каждому сектору соответствует одна из первых \(k\) букв английского алфавита, причём никаким двум секторам не соответствует одна и та же буква.
Из-за ограничений устройства сейфа пароль от него представляет собой строку длины \(n\), состоящую из только первых \(k\) букв английского алфавита. Лара вводит пароль поворачивая стрелку замка и нажимая кнопку ввода. Изначально стрелка замка указывает на секцию \(1\), а экран ввода пуст, далее за одну секунду Лара может выполнить одно из следующих действий.
- Повернуть стрелку на один сектор по часовой стрелке. Если стрелка указывала на сектор \(x < k\), то теперь она будет указывать на сектор \(x + 1\). Если же стрелка указывала на сектор \(k\), то теперь она будет указывать на сектор \(1\).
- Повернуть стрелку на один сектор против часовой стрелки. Если стрелка указывала на сектор \(x > 1\), то теперь она будет указывать на сектор \(x - 1\). Если стрелка указывала на сектор \(1\), то теперь она будет указывать на сектор \(k\).
- Нажать на кнопку ввода. В конец содержимого экрана ввода добавляется буква, соответствующая сектору, на который указывает сейчас стрелка.
Как только содержимое экрана ввода совпадёт с паролем, сейф откроется. Лара всегда действует таким образом, чтобы вводить свой пароль за минимально возможное время.
Недавно Лара узнала, что сейф можно перепрограммировать. Она может взять первые \(k\) букв английского алфавита и переназначить их секторам в произвольном порядке. Теперь она хочет переназначить буквы таким образом, чтобы свести к минимуму количество секунд, необходимых ей для ввода пароля. Вычислите это минимально возможное количество секунд, а также вычислите количество способов расставить буквы по секторам, для которых это минимальное количество секунд будет достигаться.
Два способа назначения букв секторам считаются различными, если существует хотя бы один сектор \(i\), которому в этих способах назначены разные буквы.
Выходные данные
В первой строке выведите минимально возможное количество секунд, за которое Лара введёт пароль и откроет сейф, если она оптимально расставит буквы по секторам.
Во второй строке выведите количество способов оптимально расставить буквы.
Примечание
Начальные состояния оптимальных способов для первого примера показаны на рисунке ниже.
Начальные состояния оптимальных способов для второго примера показаны на рисунке ниже.
Начальные состояния оптимальных способов для третьего примера показаны на рисунке ниже.
