小猴打架 ### 题目描述 一开始森林里面有 $N$ 只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过 $N-1$ 次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当 $N=3$ 时，就有 $\{1-2,1-3\}\{1-2,2-3\}\{1-3,1-2\}\{1-3,2-3\}\{2-3,1-2\}\{2-3,1-3\}$六种不同的打架过程。 ### 输入描述 输入一个整数 $N$。 其中，$N \leq 10^6$。 ### 输出描述 输出一行，方案数 $\mod 9999991$。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 ``` >输出 ```txt 96 ```