题目描述

求 $n$ 个点的完全图的生成树个数，树边加入的顺序不同，而最后树的形态相同时，我们认为这是两棵不同的生成树。

答案对 $9999991$ 取模。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示答案对 $9999991$ 取模后的值。

4

96

数据规模与约定

对于 $50\%$ 的数据，$1\leq n\leq 10^3$。

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