For some integers , define the "caterpillar sum" to be the following sum:
For example, the caterpillar sum for is .
Your task is to evaluate the caterpillar sum for various values of , and .
The input begins with an integer , the number of test cases. lines follow, each containing three integers .
For at least 30 points, and .
For each test case, output the caterpillar sum of , modulo .
Sample Input 1
3 5 3 1 10 1 1 10 10 1
Sample Output 1
90 55 3628800