One of the physicists was still not completely satisfied with this solution. He felt that a worker, not paying attention or not trained with the new system, could easily cause a chain reaction. He posed the question: consider a worker stacking the radioactive cubes and non radioactive cubes at random on top of each other to a height of n cubes; how many possible combinations are there for a disaster to happen?
For example, say the stack is of size 3. There is one way for the stack to reach critical mass — if all three cubes are radioactive.
1: UUU
However, if the size of the stack is 4, then there are three ways:
1: UUUL
2: LUUU
3: UUUU
The input is a list of integers on separate lines. Each integer corresponds to the size of the stack and is always greater than 0. The input is terminated with a integer value of ‘0’.
For each stack, compute the total number of dangerous combinations where each cube position in the linear stack can either be “L” for lead, or “U” for uranium. Output your answer as a single integer on a line by itself.