题目背景

翻译自 CSES-1717 题。

题目描述

有 $n$ 个孩子参加圣诞派对，每个孩子带了一个礼物。要求每个孩子都得到一个由其他人带来的礼物。

请计算有多少种方式可以分配这些礼物，使得每个孩子都得到其他孩子带来的礼物。

输入格式

唯一的输入行包含一个整数 $n$：表示孩子的数量。

输出格式

输出分配礼物的方式数目，结果对 $10^9+7$ 取模。

样例

4

9

说明/提示

$1 \leq n \leq 10^6$。