CF1391C Cyclic Permutations

A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ 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 ( $ n=3 $ but there is $ 4 $ in the array). Consider a permutation $ p $ of length $ n $ , we build a graph of size $ n $ using it as follows: - For every $ 1 \leq i \leq n $ , find the largest $ j $ such that $ 1 \leq j < i $ and $ p_j > p_i $ , and add an undirected edge between node $ i $ and node $ j $ - For every $ 1 \leq i \leq n $ , find the smallest $ j $ such that $ i < j \leq n $ and $ p_j > p_i $ , and add an undirected edge between node $ i $ and node $ j $ In cases where no such $ j $ 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 $ n = 4 $ , and $ p = [3,1,4,2] $ ; here, the edges of the graph are $ (1,3),(2,1),(2,3),(4,3) $ . A permutation $ p $ is cyclic if the graph built using $ p $ has at least one simple cycle. Given $ n $ , find the number of cyclic permutations of length $ n $ . Since the number may be very large, output it modulo $ 10^9+7 $ . Please refer to the Notes section for the formal definition of a simple cycle

N/A

N/A

There are $ 16 $ cyclic permutations for $ n = 4 $ . $ [4,2,1,3] $ is one such permutation, having a cycle of length four: $ 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4 $ . Nodes $ v_1 $ , $ v_2 $ , $ \ldots $ , $ v_k $ form a simple cycle if the following conditions hold: - $ k \geq 3 $ . - $ v_i \neq v_j $ for any pair of indices $ i $ and $ j $ . ( $ 1 \leq i < j \leq k $ ) - $ v_i $ and $ v_{i+1} $ share an edge for all $ i $ ( $ 1 \leq i < k $ ), and $ v_1 $ and $ v_k $ share an edge.