超级好玩的数列

题目背景

2012zx 特别喜欢一大堆数列，在小年的这一天，他拿出了一道题给大家。

题目描述

2012zx 有一个从 $1$ 到 $n$ 的不同正整数、按照任意顺序组成长度为 $n$ 的数列 $a$，数字分别为 $a_1$ ~ $a_n$ 。对于每一个数列，他要按照如下的方式构造一个无向图。

1. 对于每一个 $i$（$1 \le i \le n$），存在最大的 $j$（$1 \le j < i$）满足 $p_j > p_i$，在两点之间添加一条无向边。
2. 对于每一个 $i$（$1 \le i \le n$），存在最大的 $j$（$i < j \le n$）满足 $p_j > p_i$，在两点之间添加一条无向边。

其中，对于同一个点，可以连出多条无向边。

对于一个图来说，称它是“好玩的”，当且仅当根据这个排列构建的图中存在一个简单环（环的长度要大于 $2$）。

现在请你告诉 2012zx，他手里有多少个排列是“好玩的”。

由于答案可能非常大，你只需要输出答案对 $10^6+7$ 取模的结果。

输入格式

一行一个正整数 $n$，意思如题面。

输出格式

一行一个整数表示“好玩的”排列个数。

样例 #1

样例输入 #1

3

样例输出 #1

2

提示

数据范围

对于 $20\%$ 的数据，保证 $1 \le n \le 10$。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^6$。