У Кирилла было k конфет, и он захотел их раздать ученикам своей параллели. Однако заметил, что конфет у него меньше чем учеников в параллели. Кирилл сел на скамейку и задумался. Просидев полчаса и доев последнюю конфету он подумал — интересно, а сколько было способов раздать все k конфет n ученикам параллели С, если конфеты нельзя делить, а каждому школьнику можно дать не более одной конфеты.
В единственной строке записаны числа n, k(1 ≤ k ≤ n ≤ 64).
Выведите единственное число — ответ на задачу.
5 3
10
На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересоваля вопросом: «А сколько различных слов можно составить из тех же карточек, что и данное?». Помогите ему ответить на этот вопрос.
Вводится слово, составленное Петей — строка из маленьких латинских букв не длиннее 15 символов.
Выведите одно целое число — искомое количество слов.
solo
12
Пете надоело перемешивать карты для настольных игр перед каждой игрой, и он заказал по интернету специальный автоматический перемешиватель. Перемешиватель принимает на вход стопку из n карт и возвращает ее в перемешанном виде.
Вскоре друзья Пети заметили, что перемешиватель меняет порядок карт всегда одинаково. Карта, стоящая на месте i после перемешивания оказывается на месте pi. Поэтому было решено пропускать карты через перемешиватель k раз, чтобы никто из игроков не мог проследить, какая карта попала на какое место.
Однако Петя решил, что особенностью аппарата надо воспользоваться и хочет написать программу, которая посчитает, на каком месте окажется каждая карта после k перемешиваний.
Первая строка входного файла содержит целые числа n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000). Следующая строка содержит n чисел pi (1 ≤ pi ≤ n, все pi различны).
Выведите в выходной файл n чисел. i-е число должно быть равно финальной позиции карты, которая была в колоде на i месте до перемешивания.
5 2
2 3 1 5 4
3 1 2 4 5
Друзья Пети заметили, что он слишком часто выигрывает и догадались, что он написал решение предыдущей задачи. Тогда они решили увеличить ограничение на число перемешиваний до 1018, чтобы программа Пети не успевала вычислять ответ.
Помогите Пете решить задачу для больших значений k.
Формат входных и выходных данных тот же, что и в предыдущей задаче. Пример тоже можно посмотреть там. Единственное отличие этой задачи — ограничение на k ≤ 1018.
Друзья Пети поняли, что он опять мухлюет с перемешивателем и решили его проучить. Они хотят подобрать такое k, что после запуска перемешивателя раз k раз, карты встают на те же места, на которых были до перемешивания. Помогите друзьям найти минимальное такое k.
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000). Следующая строка содержит n чисел pi — перестановку, которую производит перемешиватель.
Выведите в выходной файл минимальное число раз, которое нужно запустить перемешиватель, чтобы все карты встали на исходные места.
5
2 3 1 5 4
6