Задача D. Decisive throw

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

Тимофей должен бросить n обычных шестигранных кубиков, на сторонах которых нанесены числа от 1 до 6. Если хотя бы m из них выпадут удачно, то команда друзей победит. Кубик падает удачно, если на его верхней грани выпадает число не меньше a. Например, при a = 5, n = 3 и m = 2 Тимофей для победы должен бросить три кубика таким образом, чтобы по крайней мере на двух из них выпали числа 5 или 6.

Требуется написать программу, выводящую вероятность победы друзей в виде несократимой дроби.

Формат входных данных

Единственная строка входных данных содержит три целых числа: a, n и m.

Формат выходных данных

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

Ограничения

1 ≤ a ≤ 6

1 ≤ m ≤ n ≤ 15

Пояснения к примерам

В первом примере существует 36 различных исходов выпадения двух кубиков, из них 27 являются успешными - хотя бы на одном кубике из двух выпадает число больше или равное четырем. Таким образом, вероятность успеха равна 27 / 36 или, после сокращения, 3 / 4.

Примеры тестов

Стандартный вход Стандартный выход
1
4 2 1
3 4
2
5 3 2
7 27

0.212s 0.028s 17