#描述#
A N long sequence made up of { 1,2,3, ... , N} have N! different permutations. For example , while N=3 {1,2,3}, there are 6 permutations. Sorting them by lexicographic order,they would be（1）123, （2）132,（3）213,（4）231,（5）312,（6）321. Now , give you a sequence make up of {1,2,3, ... , N}. Can you calculate its lexicographic index(1-based).

#格式#
##输入格式##
Multiple cases. For each case, first line is an integer N (1&lt=N&lt=100000), secend line contains N different integers,{ A1,A2, ... An},(1&lt=Ai&lt=N).

##输出格式##
Output its lexicographic order on a single line for each case. To make this problem easy, just output the result module 9973.

#样例1#
##样例输入1##

3
1 2 3
4
4 2 1 3

##样例输出1##

1
21

#限制#
1000ms
32768KB

#提示#

#来源#
MoonLight