In a galaxy far, far away, Rik and Vik are space adventurers who love exploring new planets. During their journey, they discovered something amazing: the size of alphabets varies from planet to planet! Excited by this, they decide to have some fun by arranging the alphabets in different patterns.

They want to arrange the letters of the alphabet in a grid with N rows and M columns. Each cell in the grid will have one letter. But they have a rule: for any group of K consecutive columns (where N x K equals the size of the alphabet), each letter of the alphabet must appear at least once.

For instance, if the alphabet size is 9 and letters are - ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘I’. For N = 3 and M = 7, here is a valid example of arrangement:

If you select any three consecutive columns you’ll be able to find all 9 letters there.

Help Rik and Vik figure out how many different ways they can arrange the alphabet following this rule.

Input starts with an integer T (T ≤ 10000) - the number of test cases. Each of the following T line consists of three integers S (1 ≤ S ≤ 10⁶), N (1 ≤ N ≤ 10⁶), and M (1 ≤ M ≤ 10⁹), where S represents the number of letters in the alphabet, N represents the number of rows in the grid, and M represents the number of columns.

Input file is large. Please be sure to use faster input/output methods.

Note that the input will follow these restrictions -

• N ≤ S
• N x M ≥ S
• S is divisible by N

For each test case, output a single integer representing the number of different arrangements possible. Since the answer may be large, output the answer modulo $10^9 + 7$.

Contest: NCPC 2023 Onsite Hosted by JU

Problem setter: Md. Arifuzzaman Arif