# #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