#552. 「LibreOJ Round #8」MIN&MAX I

题目描述

• ，且不存在 满足
• ，且不存在 满足
• ，且不存在 满足
• ，且不存在 满足

For an -order permutation , we set up an undirected simple graph with vertices numbered from to . We create an edge between each vertice and the nearest vertices in each side which correspond a greater (or less) value than .
Formally,in this graph, , the edge exists iff at least one of the following four conditions hold:

• , and no exists such that ;
• , and no exists such that ;
• , and no exists such that ;
• , and no exists such that .

Now we randomly choose a permutation from all -order permutations. Your task is to calculate the expected number of the -cycles in . You only need to output the answer modulo .

输入格式

The only line contains a positive integer which means the order of the permutation.

输出格式

Output only one line,which contains an integer which means the expected number of the -cycles in modulo .

样例输入 1

3


样例输出 1

665496236


样例输入 2

91


样例输出 2

116578319


Sample Input 1

3


Sample Output 1

665496236


Sample Explanation 1

It is easy to count that there are four -cycles in total from the permutations(each of has one). So answer is ,that is, .

Sample Input 2

91


Sample Output 2

116578319