Problem C
Contingency Planning

With two zombies, there exist four different ways that at least one can rise from the graveyard and attack.

Taking that internship in a remote mountain may not have been the best idea. Pulling that lever with the skull symbol just to see what it did was not so smart either. But now is not the time for regrets because you need to find a way to prepare for these mutant zombies fast. You need to find a way to survive and to do that you need to find a way to neutralize them.

Luckily you have some time to prepare before they rise from the cursed graveyard. You know that the graveyard will select at least one and up to $n$ graves randomly and sequentially (one by one) from which a zombie will attack.

The laboratory is equipped a machine with just enough antidote that you can use to neutralize every zombie. But here is the catch: the laboratory machine needs to produce specific and unique antidotes for each zombie in the right order.

If the wrong antidote is used, the zombie will become stronger, and you will not live to see the next day. You need to count all of the orderings of subsets of zombies, so that the machine can pre-process the required antidote sequence for every possible graveyard raid containing at least one zombie and help you plan for contingencies in any of the possible sequences.


Input consists of a single integer $1 \leq n \leq 100$, the number of cursed graves which can produce a zombie that will attack the laboratory.


Output the number of different possible orderings, and thus antidote sequences, that the zombies can raid in up to $10^9$. If the machine has to process more than $10^9$ sequences, it will crash and output JUST RUN!!

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
Sample Input 3 Sample Output 3
Sample Input 4 Sample Output 4

Please log in to submit a solution to this problem

Log in