题目描述

一开始森林里面有 $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$。

输出格式

一行，方案数 $\bmod 9999991$。

4

96

提示

$50\%$ 的数据 $N\le 10^3$。
$100\%$ 的数据 $N\le10^6$。