Trong một buổi tối u ám, bạn đối đầu với một nhà ảo thuật tên là Rex trong một trận đấu ẩn số để kiểm tra tài năng phân tích của mình. Nhà ảo thuật Rex đưa ra một bàn chơi với ~N~ hộp giống nhau và một viên thuốc ma thuật được giấu vào một trong số chúng. Sau khi ăn thuốc này bạn sẽ không bao giờ gặp lỗi biên dịch nữa. Nhiệm vụ của bạn trong màn đấu này là tìm ra chiếc hộp chưa viên thuốc đó. Bạn có tối đa ~M~ lượt chơi. Trong mỗi lượt, bạn có thể chọn một trong hai hành động sau:

• Hành động 1: Chọn một trong các hộp trước mặt cậu ấy một cách ngẫu nhiên và đoán rằng hộp này có chứa viên thuốc. Nếu đoán đúng, bạn sẽ nắm giữ ngay lập tức chiếc vé tới thế giới không lỗi biên dịch. Nhưng nếu đoán sai, nhà ảo thuật tức tốc thổi thêm vào trò chơi ~K~ chiếc hộp trống. Những chiếc hộp mới kia, trở thành một thách thức đối với khả năng phân biệt của anh, anh ấy sẽ không thể nhận ra hộp này với các hộp khác trong các lượt tiếp theo.

• Hành động 2: Chọn một số ~X~ - một bội số của ~K~ và đồng thời nhỏ hơn số lượng hộp mà anh ta đang đối mặt. Nhà ảo thuật Rex, sau đó tiến hành loại bỏ đúng ~X~ chiếc hộp trống. Tất nhiên, bạn không thể thực hiện thao tác này nếu số hộp hiện tại không vượt qua ngưỡng ~K~.

Nhiệm vụ của bạn là tính xác suất tối đa tìm được viên thuốc, giả sử bạn luôn chơi tối ưu.

Kết quả cần biểu diễn dưới dạng phân số ~\frac{P}{Q}~, trong đó ~P, Q~ nguyên tố cùng nhau.
Hãy in ra giá trị ~P \cdot Q^{-1} \bmod (10^9+7)~, trong đó ~Q^{-1}~ là nghịch đảo của ~Q~ khi lấy phần dư với ~10^9+7~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~T~ ~(1 \le T \le 10^5)~ — số bộ test.
• Mỗi dòng trong ~T~ dòng tiếp theo chứa 3 số nguyên ~N, K, M~ với ràng buộc:
  ~1 \le N < K \le 3 \cdot 10^4,~
  ~1 \le M \le 3 \cdot 10^4~.

Dữ liệu ra

• Với mỗi test, in ra một số nguyên duy nhất: giá trị ~P \cdot Q^{-1} \bmod (10^9+7)~.

Sample Input

3 
5 9 1 
7 9 2 
3 20 3

Sample output

400000003
196428573
555555560

Giải thích

• Ví dụ 1: Bạn chỉ có 1 lượt chơi, do đó chỉ có thể đoán trực tiếp. Xác suất đúng là ~\tfrac{1}{5}~.
• Ví dụ 2:
  
  • Lượt 1: đoán, xác suất đúng ~\tfrac{1}{7}~. Nếu sai (xác suất ~\tfrac{6}{7}~), số hộp tăng thành 16.
  • Lượt 2: đoán, xác suất đúng lúc này ~\tfrac{1}{16}~.
    Tổng xác suất = ~\tfrac{1}{7} + \tfrac{6}{7} \cdot \tfrac{1}{16} = \tfrac{11}{56}~.
• Ví dụ 3:
  
  • Lượt 1: đoán, xác suất đúng ~\tfrac{1}{3}~.
  • Nếu sai, yêu cầu ảo thuật loại bỏ ~X = 20~ hộp, còn lại 3 hộp.
  • Lượt 3: đoán tiếp, xác suất đúng ~\tfrac{1}{3}~.
    Tổng xác suất = ~\tfrac{1}{3} + \tfrac{2}{3} \cdot \tfrac{1}{3} = \tfrac{5}{9}~.