«Получай!» — крикнул Финн, сражаясь с Теневыми Стражами, — «Джейк! Быстрее собирай Камни Тьмы и бежим отсюда!»

Джейк был бы рад закончить побыстрее, ведь в Опасной Пещере было сыро и грустно, но сбор Камней оказался не такой уж простой задачей. Поэтому он позвонил БиМо и попросил его помочь выбрать оптимальный набор Камней. Джейк рассказал БиМо о том, что всего в пещере лежат n камней, пронумерованных различными целыми числами от 1 до n, каждый из которых покрашен в один из 26 цветов. Также Джейк напомнил БиМо о предупреждении принцессы Бубльгум: среди вынесенных из пещеры Камней должно быть не более k штук, имеющих попарно различные цвета. Только множество Камней, обладающее этим свойством, является безопасным. Если же вынести из пещеры небезопасное множество Камней, будет разбужено Вселенское Зло! Разумеется, Джейк не хочет будить Зло, но хочет вынести как можно больше Камней Тьмы из Пещеры. Попробуйте поставить себя на место БиМо и найдите размер наибольшего безопасного множества Камней и количество различных безопасных множеств такого размера. Два множества Камней следует считать различными, если в одном из них есть Камень с номером, которого нет в другом множестве.

В первой строке записано n строчных латинских букв (1 ≤ n ≤ 10⁵), каждая буква обозначает цвет Камня. Во второй строке дано целое число k (1 ≤ k ≤ 26).

Выведите два целых числа, разделённых пробелом: размер наибольшего безопасного множества Камней Тьмы и количество различных безопасных множеств такого размера.