Counting Good Representative Schemes

Let ( U = {1, 2, \ldots, n} ) be the universal set. We define an operation scheme as a function that assigns to every nonempty subset ( S \subseteq U ) a representative element ( r(S) ) chosen from ( S ). An operation scheme is called good if and only if for every nonempty subset ( S \subseteq U ) and for every partition of ( S ) into ( m ) nonempty subsets ( A_1, A_2, \ldots, A_m ), there exists at least one index ( i ) (with ( 1 \le i \le m )) such that ( r(A_i) = r(S) ).

It can be proven that an operation scheme is good if and only if for every nonempty subset ( S \subseteq U ) with ( r(S)=x ), one must have ( r(T)=x ) for every nonempty ( T \subseteq S ) that contains ( x ). In particular, if we take ( S = U ) and let ( r(U)=x ), then the condition forces ( r(T)=x ) for every nonempty subset ( T \subseteq U ) that contains ( x ). Consequently, the choices for a good scheme are entirely determined by the choice of ( x ) for ( U ) (which has ( n ) options) and by independently choosing a good scheme on ( U\setminus{x} ). Thus, if we denote by ( f(n) ) the number of good schemes on ( U ) with ( |U| = n ), we have the recurrence:

[ f(n) = n \cdot f(n-1) \quad \text{with} \quad f(0)=1. ]

It follows that ( f(n) = n! ). Your task is to compute ( n! ) modulo ( 1000000087 ).

Note: Two operation schemes are considered essentially different if there exists some nonempty set ( S \subseteq U ) such that the representatives ( r(S) ) in the two schemes differ.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁶ or as specified in the problem constraints) which represents the size of the set \( U = \{1, 2, \ldots, n\} \).

outputFormat

Output a single integer, the value of \( n! \) modulo \( 1000000087 \).

sample

1

1