#CS1717. 圣诞派对

圣诞派对

题目背景

翻译自 CSES-1717 题。

题目描述

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

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

输入格式

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

输出格式

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

样例

4

9

说明/提示

1≤n≤106。