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?

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 ≤ 10¹²; 1 ≤ k ≤ 10¹⁸; min(n, m) ≤ 10⁶) which are the number of sockets on the field’s south border, on its west border and the capacity of the bucket.

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

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.