|
Три кучки камней
(Время: 0,25 сек. Память: 32 Мб Сложность: 63%)
Есть три кучки камней размеров a, b, c. Пока все три кучки положительные, за один шаг выбирается одно из 6 действий равновероятно перекладывается ровно 1 камень из одной кучки в другую:
- b→a: (a + 1, b − 1, c)
- a→b: (a − 1,b + 1, c)
- a→c: (a − 1, b, c + 1)
- c→a: (a + 1, b, c − 1)
- c→b: (a, b + 1, c − 1)
- b→c: (a, b − 1, c + 1)
Процесс останавливается, как только хотя бы одна кучка стала равной нулю. Вам дано T независимых запросов. Для каждого запроса выведите математическое ожидание числа шагов до остановки по модулю 109 + 7.
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число T - число запросов. Далее в T строках содержится по три числа a, b, c. (1 ≤ T ≤ 2×105; 1 ≤ a, b, c ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на каждый запрос по модулю 109 + 7 через пробел.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
4 2 3
5 1 3
3 3 3 | 8 5 9 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
