A permutation of length ? is an array consisting of ? distinct integers from 1 to ? in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (?=3 but there is 4 in the array).
Consider a permutation ? of length ?, we build a graph of size ? using it as follows:
For every 1≤?≤?, find the largest ? such that 1≤?<? and ??>??, and add an undirected edge between node ? and node ?
For every 1≤?≤?, find the smallest ? such that ?<?≤? and ??>??, and add an undirected edge between node ? and node ?
In cases where no such ? exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.
For clarity, consider as an example ?=4, and ?=[3,1,4,2]; here, the edges of the graph are (1,3),(2,1),(2,3),(4,3).
A permutation ? is cyclic if the graph built using ? has at least one simple cycle.
Given ?, find the number of cyclic permutations of length ?. Since the number may be very large, output it modulo 109+7.
Please refer to the Notes section for the formal definition of a simple cycle
Input
The first and only line contains a single integer ? (3≤?≤106).
Output
Output a single integer 0≤?<109+7, the number of cyclic permutations of length ? modulo 109+7.
Examples
inputCopy
4
outputCopy
16
inputCopy
583291
outputCopy
135712853
Note
There are 16 cyclic permutations for ?=4. [4,2,1,3] is one such permutation, having a cycle of length four: 4→3→2→1→4.
Nodes ?1, ?2, …, ?? form a simple cycle if the following conditions hold:
?≥3.
??≠?? for any pair of indices ? and ?. (1≤?<?≤?)
?? and ??+1 share an edge for all ? (1≤?<?), and ?1 and ?? share an edge.
题意：
一个排列，每个下标向左右最近的大于他的数连边（下标连边）。多少个排列成环。
思路：
通过模拟可以发现，只要有X，X-delta，X+delta这种形式出现，那就一定成环。
所以不成环的情况就是一直上升，然后再一直下降的情况。
我们考虑最大的数摆在第
个位置，那么还需要选择i-1个数摆在左边。
所以是
，求和以后是
。
所以结果是
#pragma GCC optimize(2)#include<iostream>
#include<cstdio>
#include <map>
#include<cstring>
#include <map>
#include <math.h>
#include<queue>
#include <algorithm>using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 7;
typedef long long ll;ll fac[maxn],p[maxn];
int main() {int n;scanf("%d",&n);ll ans = 1;fac[0] = 1;p[0] = 1;for(int i = 1;i <= n;i++) {fac[i] = fac[i - 1] * i % mod;p[i] = p[i - 1] * 2 % mod;}ans = (fac[n] - p[n - 1] + mod) % mod;printf("%lld\n",ans);return 0;
}