Обычно в игру «Бинго!» играют на доске 5 × 5, заполненной различными целыми числами от 1 до 75. В этой задаче мы будем рассматривать обобщенную модель игры «Бинго!». Действие игры будет происходить на доске n × n, заполненной различными целыми числами от 1 до m (m ≥ n2).
Рассмотрим следующий случайный процесс. Изначально генерируется случайная доска для игры (равновероятно среди всех досок). Затем случайным образом выбираются k различных чисел от 1 до m (равновероятно среди всех наборов из k различных чисел). Те из этих чисел, которые встречаются на сгенерированной доске, помечаются. Выигрышем будем называть число: два в степени [количество строк, целиком состоящих из помеченных чисел, плюс количество столбцов, целиком состоящих из помеченных чисел].
Ваша задача посчитать математическое ожидание выигрыша в описанном случайном процессе для заданных n, m, k. Полученное математическое ожидание может быть очень большим, поэтому если оно превышает 1099, выведите 1099 вместо ответа (например, можно вывести строку «1e99» без кавычек).
Выходные данные
Выведите математическое ожидание выигрыша или 1099, если математическое ожидание превышает это значение. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10 - 9.