ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2043. Kirill the Gardener 2

Time limit: 4.0 second
Memory limit: 64 MB
Today is the third moon day, so it’s time to plant potato! Gardener Kirill stands on a huge rectangle potato field which has n × m sockets. Distance between two adjacent sockets equals one step. Luckily, they are already dug up. Also, Kirill has a bucket big enough to hold k potatoes.
Kirill is a very organized young man, so he plants potatoes using a strict algorithm. He starts from south-west corner and moves to the north until he reaches the end of the field. Then he takes one step east and moves to the south border of the field. After that, he takes one more step east. He repeats these steps while there are still unprocessed sockets. However, the volume of his potato bucket is limited, so after each k sockets, Kirill has to go to the south border of the field and then one step out of the field to fill the bucket again (there are infinitely many potatoes outside the south border of the field). After that, he makes one step north to return to the socket from which he left the field, and then goes to the next unprocessed socket using the shortest path (Kirill comes from Manhattan and can move only parallel to coordinate axes). Surely, if the bucket becomes empty after Kirill plants a potato in the last socket, he won’t go back for more potatoes. How many steps will our young gardener make?
Problem illustration

Input

The first line contains the number of test cases: an integer t from 1 to 10. Next t lines contain test cases, one test case per line. Each test case line contains three integers n, m, k (1 ≤ n, m ≤ 1012; 1 ≤ k ≤ 1018; min(n, m) ≤ 106) which are the number of sockets on the field’s south border, on its west border and the capacity of the bucket.

Output

For each test case, print one line containing the answer modulo 109 + 7.

Sample

inputoutput
1
5 3 5
20

Notes

The sequence of visited squares will be as follows: 1, 2, 3, 4, 5, 6, out, 6, 7, 8, 9, 10, 11, 12, out, 12, 11, 12, 13, 14, 15 (see the picture). So, the total number of steps is 20.
Problem Author: Ilya Kuchumov (Prepared by Kirill Borozdin)
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014