Description

Initially, there are $N$ little monkeys in the forest who do not know each other. They often fight, but the two sides in a fight must not be good friends. After each fight, the two fighters and their respective good friends will get to know each other and become good friends with each other. After $N - 1$ fights, all the monkeys in the forest will become good friends. The question is: how many different fighting processes are there in total. For example, when $N = 3$, there are six different fighting processes: {1-2, 1-3} {1-2, 2-3} {1-3, 1-2} {1-3, 2-3} {2-3, 1-2} {2-3, 1-3}.

Input Format

A single integer $N$.

Output Format

One line: the number of ways $\bmod 9999991$.

4

96

Hint

• 50% of the testdata $N \le 10^3$.
• 100% of the testdata $N \le 10^6$.

Translated by ChatGPT 5