Многие преподаватели считают, что тестирование лабораторных работ, выполняемых студентами, совсем необязательно. Разве можно не поставить зачёт студенту, если у него есть отчёт с распечатанным программным кодом и какие-никакие теоретические познания? В конечном итоге студенты привыкают, что программный код совсем не обязательно отлаживать, и очень часто пытаются сдавать абсолютно неработоспособные программы.

В рамках одной из лабораторных работ от студента требовалось реализовать структуру данных, которая бы инициализировалась неубывающей последовательностью из N чисел, и поддерживала следующие типы запросов:

1. Удалить M-й элемент в порядке возрастания из последовательности.

2. Определить, какое число является K-м по возрастанию в текущей последовательности.

Вместо того чтобы изучить теорию и написать новую структуру, студент решил упростить себе задачу, поместив все элементы последовательности в обычный массив без изменений и реализовав ответы на запросы следующим образом:

1. Поменять местами M-й элемент массива с последним элементом массива, после чего удалить последний элемент из массива.

2. Вернуть K-й элемент массива.

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

Сегодня студентов, пришедших сдавать лабораторные работы, очень много, и поэтому аспирант вынужден тестировать каждую программу следующим образом: на вход подаётся некоторая последовательность чисел A, затем выполняется один запрос 1-го типа (выполняется условие 1 ≤ M ≤ N), а после него — один запрос 2-го типа (выполняется условие 1 ≤ K ≤ N - 1). Лабораторная работа считается зачтённой, если программа выдаст правильный ответ на выполненный запрос 2-го типа.

От однокурсников студент узнал последовательность чисел A, на которой выполняется тестирование всех программ, однако значения M и K узнать не удалось — аспирант выбирает их случайным образом равновероятно из всего множества допустимых значений.

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