Сегодня третьи лунные сутки, а значит, самое время сажать картошку! И вот садовод Кирилл уже стоит на большом картофельном поле, имеющем вид прямоугольника n на m. Он мысленно разделил его на единичные квадраты (клетки). В центре каждой клетки раскопана лунка. У нашего героя есть ведёрко, вмещающее не более k картофелин, в руках он картошку не носит. Для перехода между двумя клетками, имеющими общую сторону, Кириллу нужен один шаг. Для выхода за границу поля с клетки, находящейся на границе, ему также требуется один шаг. Если он вышел за границу поля, то возвращается он в ту же клетку, с которой попал туда, для этого ему снова нужен один шаг.

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

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

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

Последовательность посещённых клеток в примере будет выглядеть так: 1, 2, 3, 4, 5, 6, out, 6, 7, 8, 9, 10, 11, 12, out, 12, 11, 12, 13, 14, 15 (см. рисунок). Итого будет совершено 20 шагов.