C. 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

样例解释 1

在所有 种排列中共有 个三元简单环（ 各一个），所以答案为 ，即 。

样例输入 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

对于所有数据，。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

For all test cases, .

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):