Domino

Find the number of ways to completely tile a rectangle of size 2 \times n with dominoes of size 2 \times 1. Coverings that coincide with themselves under symmetries (rotations or reflections) are considered different.

Output

Print the number of ways to tile the rectangle with dominoes.