Олимпиадный тренинг

Задача . E. Супер-Бомбардир


Хасан любит различные игры, и недавно его заинтересовала игра под названием Супер-Бомбардир. В этой игре (которая довольно похожа на футбол) \(p\) игроков бьют пенальти. Победитель — это тот игрок, который забил наибольшее число голов. В случае ничьи, один из игроков, забивших наибольшее число голов, объявляется победителем равновероятно.

Игроки только закончили матч, и теперь ожидают результата. Однако закралась небольшая проблема! Судьи потеряли таблицу с счетом всех игроков! К счастью, до потери они успели посчитать сумму забитых голов, а также для каждого игрока они запомнили нижнюю границу на количество забитых им голов. Однако информация об этих границах конфиденциальна, поэтому Хасан смог узнать только свою нижнюю границу.

Согласно предоставленной информации, он знает, что его счет не меньше \(r\), а сумма счета всех игроков — \(s\).

Поэтому финальное состояние игры может быть записано в виде последовательности \(p\) целых чисел \(a_1, a_2, \dots, a_p\) (\(0 \le a_i\)) — счет игроков. Хасан — игрок номер \(1\), поэтому \(a_1 \ge r\). К тому же \(a_1 + a_2 + \dots + a_p = s\). Два состояния считаются различными, если существует такая позиция \(i\), что значение \(a_i\) различается в этих двух состояниях.

Еще раз, Хасан не знает точного счета игроков (он не знает и свой точный счет). Поэтому он считает, что вероятность получить любое финальное состояние игры одинакова.

Помогите Хасану найти вероятность его победы.

Можно показать, что она может быть представлена в форме \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа и \(Q \ne 0\), \(P \le Q\). Сообщите значение \(P \cdot Q^{-1} \pmod {998244353}\).

Входные данные

В единственной строке записаны три целых числа \(p\), \(s\) и \(r\) (\(1 \le p \le 100\), \(0 \le r \le s \le 5000\)) — количество игроков, сумма счета всех игроков и счет Хасана, соответственно.

Выходные данные

Выведите единственное число — вероятность победы Хасана.

Можно показать, что она может быть представлена в форме \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа и \(Q \ne 0\), \(P \le Q\). Сообщите значение \(P \cdot Q^{-1} \pmod {998244353}\).

Примечание

В первом примере Хасан мог забить \(3\), \(4\), \(5\) или \(6\) голов. Если он забил \(4\) гола или больше, то его счет будет строго больше счета единственного соперника. Если он забил \(3\), то и его соперник забил \(3\), и вероятность победы Хасана равна \(\frac 1 2\). Следовательно, итоговая вероятность победы Хасана равна \(\frac 7 8\).

Во втором примере даже нижняя граница на счет Хасана подразумевает, что он забил больше, чем любой из его соперников. Следовательно, итоговая вероятность победы Хасана равна \(1\).


Примеры
Входные данныеВыходные данные
1 2 6 3
124780545
2 5 20 11
1
3 10 30 10
85932500

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя