小猴打架

一开始森林里面有 $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$ 取模的结果。

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