← 返回题目

题库练习小猴打架

← 上一题下一题 →

A2710 | $小猴打架$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出