Alice was given the integers from to . She wrote all possible permutations in increasing lexicographical order, and wrote each permutation in a new line. For example, for , there are possible permutations:

She then chose one permutation among them as her favorite permutation.

After some time, she forgot some elements of her favorite permutation. Nevertheless, she still tried to write down its elements. She wrote a in every position where she forgot the true value.

She wants to know the sum of the line numbers of the permutations which could possibly be her favorite permutation, i.e., permutations which can be obtained by replacing the s. Can you help her out?

Since the sum can be large, find it modulo .