[SOJ 1141]猴子的争斗

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 merge.in 输出文件 merge.out

【问题描述】

从前，在一个森林里有N只好斗的猴子。开始，它们互不认识。互不认识的猴子间是无法避免争斗的，而且争斗只会发生在两只互不认识的猴子间。决斗结束后，这两只猴子和它们各自的朋友们通过这场决斗相互间都认识了，争斗便不会再在这一大群猴子中的任意两只之间发生。

由于决斗是比较激烈的，所以同一时间内不会有两场决斗同时发生。经过N-1次决斗后，这N只猴子间相互都认识了，问有多少种可能的决斗过程。例如N=3，有6种不同的过程：12～13，12～23，13～12，13～32，23～21，23～3l。


【输入】

输入格式(输入文件名merge．in)

文件里只有一个整数N(2≤N≤1000)。


【输出】

输出格式(输出文件名merge．out)、

输出一个整数，为可能的过程的总数除以10007的余数。


【输入输出样例】

输入(merge．in)

4

输出(merge．out)

96