A single row has n parking spots in a line. Each spot is either empty or holds one car. For safety, no two occupied spots may be next to each other. Count the number of valid occupancy patterns for the whole row. The empty row (all spots empty) counts as one valid pattern. The answer always fits in a 64-bit integer for the given constraints, so print the exact count (no modulo).
Input format
A single line with one integer n.
Output format
A single integer: the number of valid occupancy patterns.
Constraints
- 0 <= n <= 30