题目描述
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj. Consider such sequences which only contains 1, 2, 3...n, we know that there are n! different sequences.You are giver a integer n, and your task is to count the sum of the inversion number of all the sequences.As the answer may be very large, you only need to output the answer mod 9973.
输入
The first line is integer T(T <= 1000), the number of test cases.Then T lines, each lines contains a integer n (n <= 10^9).
输出
For each case, output the sum of the inversion number of all the sequences mod 9973 in the sample output format.
Case #1: 0
Case #2: 1
Case #3: 9
提示
The third case:
n=3, so there are 6 different sequences,
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
the sum of inversion number is 0 + 1 + 1 + 2 + 2 + 3 = 9