#OJ1631. Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

小K周末参加了一个娱乐活动。在这个活动中,主持人选出n个人,并将这些人从1到n编号,让他们组成一个排列。如果按字典序来排列,这n个人的排列是第几个?结果可能很大,你只需要输出模1000000007的结果就OK了。 For example 1 2 3 -> 1 1 3 2 -> 2 2 1 3 -> 3 2 3 1 -> 4 3 1 2 -> 5 3 2 1 -> 6

Input

多组数据 每组第一行输入一个整数n(0<n<=1000) 每组第二行输入一个1——n的排列

Output

每组输出一行,包含一个正整数,表示排列的顺序数模1000000007的结果

Sample Input

3
1 2 3

Sample Output

1

HINT

Append Code

Source