A nice entertainment was invented in the kindergarten. Each child has to bring a present from his home — a big box with something interesting inside. Contents of the boxes shall be kept secret up to the last
moment. After that the chidren will exchange their presents.
Children understood that they would have to part with their presents so they stuffed their boxes with
useless junk: candy wrappers, husk, broken computer mice and even unnecessary elder brother's fat book
with some kind of donkey on the cover.
So, a child didn't mind parting with his box. Moreover, he didn't calm down until he made sure he got
rid of his box. Having foisted his box off, no child ever took it back. If some kid didn't get a present in
exchange for his own one, he would become very disappointed and his loud cries would attract attention
of a nurse who had to take away all those boxes along with the marvellous content!
As a chief information officer of entertainment operations, you are to find out the amount of the present
exchange schemes such that each child would be pleased. But there is one hitch
Your hand-book on
algorithms was taken by your younger brother to his kindergarten for some purpose. Sixteenth chapter
might prove very useful
One number n (1 ≤ n ≤ 1000) — the amount of children in the kindergarten.
One number — the amount of exchange schemes. E.g., for three presents A, B and C there are only two exchange schemes:
- Box A goes to the child B, box B — to the child C and box C — to the child A.
- Box A goes to the child C, box C — to the child B and box B — to the child A.
Problem Author: Pavel Egorov (idea by Stanislav Vasilyev)
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005