Tied Permutations

Hermione is fascinated by the ongoing competitions between the four houses at Hogwarts. “This year, our house wins, and others come in second, third, and fourth. How many ways are there to order our houses in the competition?” “24, right?” says Harry. “That's four factorial.” (“Duh,” pipes in Ron.) “It seems like 24 at first glance, but it's more than that,” says Hermione, “because houses can tie in competition. Suppose there were only two houses competing: G and S. G can beat S, S can beat G, or they can tie. That's three ways to order them! If we throw house R into the competition, there are six ways they can finish without ties [“6 is three factorial,” interrupts Harry.]; G and S can tie, G and R can tie, R and S can tie, and they can either tie for first or tie for second, so that's another six ways; and there can be a three-way tie! There are 13 ways to order three houses!”

If there are n houses (or teams) competing, how many ways are there for them to finish?

Input Specification

The input will consist of integers inclusively between 1 and 10. Each integer will be followed by exactly one newline character. The final line in the input will consist of a single 0. This line indicates the end of input and is not to be processed.

Output Specification

The output cases are to appear in the same order in which they appear in the input. For each input integer n, the output will be the integer indicating the number of ways to order n teams when ties are taken into consideration. Each output integer is to be followed by exactly one newline character.

Sample Input

1. 2
2. 3
3. 0

download as text file

Output for Sample Input

1. 3
2. 13

download as text file

Original Problem

NMU Invitational Programming Contest, 2001