There are positive integers and another positive integers .
Let be a permutation of . Initially, the entire number line is white. For each , the segment is colored black. is then defined as the total length of black segments on the number line. For example, if is colored black, then the total length of black segments is .
Find the sum of over all permutations of , modulo .
输入格式
The first line of input contains a single integer ().
The second line of input contains space-separated integers ().
The third line of input contains space-separated integers ().
输出格式
Output a single integer, the sum of over all permutations of , modulo .
Sample 1: There are permutations of length 3. Let be the permutation.
: the segments are , , , total length = .
: the segments are , , , total length = .
: the segments are , , , total length = .
: the segments are , , , total length = .
: the segments are , , , total length = .
: the segments are , , , total length = .
The answer is .
Sample 2: There is only one permutation, and the only segment is . The answer is .
Sample 3: Note that there may be duplicate values. Different permutations may create the same sequence, and you should still count them multiple times (as though as they are different).
Sample 4: This fits the constraints of Subtask 1.
Sample 5: Remember to output the answer modulo .
Scoring
Subtask 1 ( points): All are equal, i.e. for all ()
