小猴打架

一开始森林里面有 $N$ 只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。

每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过 $N-1$ 次打架之后，整个森林的小猴都会成为好朋友。

现在的问题是，总共有多少种不同的打架过程。

比如当 $N=3$ 时，就有

$$\{1\text{-}2,\ 1\text{-}3\},\quad \{1\text{-}2,\ 2\text{-}3\},\quad \{1\text{-}3,\ 1\text{-}2\},$$ $$\{1\text{-}3,\ 2\text{-}3\},\quad \{2\text{-}3,\ 1\text{-}2\},\quad \{2\text{-}3,\ 1\text{-}3\}$$

六种不同的打架过程。

输入格式

一个整数 $N$。

输出格式

一行，方案数对 $9999991$ 取模的结果。

样例输入

4

样例输出

96

数据范围

• $N\le 10^6$。

来源与许可

本题题面与测试数据整理自 BZOJ 1430。