今天是农历初三，是种土豆的好日子！园丁基里尔（Kirill）站在一个巨大的矩形土豆田里，田里有 $n \times m$ 个坑。相邻两个坑之间的距离为一步。幸运的是，这些坑都已经挖好了。此外，基里尔有一个能装 $k$ 个土豆的桶。

基里尔是一个非常有条理的年轻人，他按照严格的算法种植土豆。他从西南角开始，向北移动，直到到达田地的尽头。然后他向东走一步，再向南移动到田地的南边界。之后，他再向东走一步。只要还有未处理的坑，他就重复这些步骤。然而，他的土豆桶容量有限，因此每种完 $k$ 个坑后，基里尔必须前往田地的南边界，然后走出田地一步去重新装满桶（田地南边界外有无穷多的土豆）。装满后，他向北走一步回到他离开田地时的那个坑，然后使用最短路径前往下一个未处理的坑（基里尔来自曼哈顿，只能平行于坐标轴移动）。当然，如果基里尔在种完最后一个坑后桶空了，他不会再回去装土豆。请问我们的年轻园丁总共要走多少步？

输入格式

第一行包含测试用例的数量：一个整数 $t$（$1 \le t \le 10$）。接下来 $t$ 行包含测试用例，每行一个测试用例。每个测试用例包含三个整数 $n, m, k$（$1 \le n, m \le 10^{12}$；$1 \le k \le 10^{18}$；$\min(n, m) \le 10^6$），分别表示田地南边界上的坑数、西边界上的坑数以及桶的容量。

输出格式

对于每个测试用例，输出一行，包含答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

10
5 3 5
10 1 2
1 110 1
3 999 17
879 12 7
765 97 345
333 333 333
101 107 9999
100 100 5
557 139 78

输出 1

20
17
12099
179524
28745
95142
221776
10924
210097
215376

说明

访问方格的顺序如下：1, 2, 3, 4, 5, 6, out, 6, 7, 8, 9, 10, 11, 12, out, 12, 11, 12, 13, 14, 15。因此，总步数为 20。