Аудит серверов
(Время: 0,5 сек. Память: 64 Мб Сложность: 89%)
Алексей проводит аудит серверов в Q компаниях.
В компании есть N серверов. Каждый сервер либо подключён к защищённому сегменту сети, либо отключён от него. В начале все серверы отключены. В течение квартала отдел информационной безопасности проводит ровно m запланированных изменений конфигурации. Каждое изменение оформляется как официальный запрос. В одном таком запросе можно указать любой набор серверов, для которых нужно изменить состояние подключения: если сервер был подключён – его отключают, если был отключён – подключают. То есть каждый запрос «переключает» состояние выбранных серверов.
По правилам компании:
- нельзя дважды оформлять один и тот же набор серверов в разных запросах;
- каждый запрос должен отличаться от всех остальных.
После выполнения всех M изменений необходимо чтобы первые K серверов (важные системы) были подключены к защищённой сети, а остальные серверы должны оставаться отключёнными. Если это условие не выполнено – аудит считает проект проваленным.
Если в обоих случаях используются одни и те же наборы серверов, просто применённые в разной последовательности, – это один и тот же план.
Помогите Алексею определить количество различных планов изменений, которые приведут к требуемому результату для каждой компании.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число Q, далее в Q строках по три натуральных числа N, M, K (1 ≤ Q ≤ 2×105; 1 ≤ N, M ≤ 108; 0 ≤ K ≤ N).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ для каждой компании по модулю 6972593.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
4 3 2
3 2 1
3 3 0
3 3 1
4 2 1 | 35
4
7
7
8 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
