ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2043. Садовод Кирилл 2

Ограничение времени: 4.0 секунды
Ограничение памяти: 64 МБ
Сегодня третьи лунные сутки, а значит, самое время сажать картошку! И вот садовод Кирилл уже стоит на большом картофельном поле, имеющем вид прямоугольника n на m. Он мысленно разделил его на единичные квадраты (клетки). В центре каждой клетки раскопана лунка. У нашего героя есть ведёрко, вмещающее не более k картофелин, в руках он картошку не носит. Для перехода между двумя клетками, имеющими общую сторону, Кириллу нужен один шаг. Для выхода за границу поля с клетки, находящейся на границе, ему также требуется один шаг. Если он вышел за границу поля, то возвращается он в ту же клетку, с которой попал туда, для этого ему снова нужен один шаг.
Кирилл прямолинеен, поэтому сажает картошку, строго следуя определённому алгоритму. Он начинает в юго-западном углу поля и идёт на север, пока не дойдёт до северного края поля. Затем он делает один шаг на восток и идёт на юг, пока не дойдёт до южного края поля. Затем он вновь делает один шаг на восток. После этого всё повторяется, пока Кирилл не посетит последнюю клетку поля. Но вместимость ведёрка ограничена, поэтому через каждые k пройденных лунок Кириллу приходится идти на юг до последнего ряда. Вдоль всей южной границы поля рассыпаны горы картошки. Кирилл выходит за границу поля, там он наполняет своё ведёрко и идёт к следующей в порядке обхода клетке по кратчайшему пути (Кирилл — уроженец Манхеттена, поэтому он может двигаться только параллельно осям координат). Если его ведро опустеет в последней клетке, он не пойдёт за новой порцией картофеля. Сколько шагов совершит юный садовод?
Problem illustration

Исходные данные

В первой строке дано количество тестовых примеров — целое число t от 1 до 10. Далее в следующих t строках расположены тесты. Каждый тест состоит из одной строки. Все последующие строки содержат по три числа n, m, k (1 ≤ n, m ≤ 1012; 1 ≤ k ≤ 1018; min(n, m) ≤ 106) — количество лунок в поле по направлению с запада на восток, количество лунок в поле по направлению с юга на север и вместимость ведёрка соответственно.

Результат

Для каждого примера выведите ответ по модулю 109 + 7.

Пример

исходные данныерезультат
1
5 3 5
20

Замечания

Последовательность посещённых клеток в примере будет выглядеть так: 1, 2, 3, 4, 5, 6, out, 6, 7, 8, 9, 10, 11, 12, out, 12, 11, 12, 13, 14, 15 (см. рисунок). Итого будет совершено 20 шагов.
Автор задачи: Илья Кучумов (Подготовка — Кирилл Бороздин)
Источник задачи: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014