Обычно в игру «Бинго!» играют на доске 5 × 5, заполненной различными целыми числами от 1 до 75. В этой задаче мы будем рассматривать обобщенную модель игры «Бинго!». Действие игры будет происходить на доске n × n, заполненной различными целыми числами от 1 до m (m ≥ n²).

Рассмотрим следующий случайный процесс. Изначально генерируется случайная доска для игры (равновероятно среди всех досок). Затем случайным образом выбираются k различных чисел от 1 до m (равновероятно среди всех наборов из k различных чисел). Те из этих чисел, которые встречаются на сгенерированной доске, помечаются. Выигрышем будем называть число: два в степени [количество строк, целиком состоящих из помеченных чисел, плюс количество столбцов, целиком состоящих из помеченных чисел].

Ваша задача посчитать математическое ожидание выигрыша в описанном случайном процессе для заданных n, m, k. Полученное математическое ожидание может быть очень большим, поэтому если оно превышает 10⁹⁹, выведите 10⁹⁹ вместо ответа (например, можно вывести строку «1e99» без кавычек).