UVa 10862

10862 - Connect the Cable Wires

• http://acm.uva.es/p/v108/10862.html

Summary

To find number of ways to connect a center with many houses with cables directly or via houses.

Explanation

Take paper and pencil and draw all the cable connection possibilities for the first few number of houses. The result should somewhat resemble the Fibonacci Sequence.

Notes

• The output for any given case will be at most 900 digits.

Input

1
2
3
20
0

Output

1
3
8
102334155