Banquet Table Arrangements

At a grand banquet, the host wishes to seat guests along a long table, with the restriction that no two guests can be seated directly next to each other. Given a table with ( n ) seats, determine the number of ways to arrange the guests under this rule. It turns out that the number of valid arrangements follows a recurrence relation similar to the Fibonacci sequence. Specifically, if we denote ( f(n) ) as the number of ways to arrange guests for ( n ) seats, then:

[ f(n) = f(n-1) + f(n-2) \quad \text{for } n \geq 2, ]

with base conditions defined as ( f(0)=1 ) and ( f(1)=1 ). Notice that for ( n \ge 1 ), the answer is equivalent to the ( (n+1) )-th Fibonacci number. Your task is to implement a solution that reads an integer ( n ) from the standard input and prints the number of valid seating arrangements to the standard output.

inputFormat

The input consists of a single line containing one integer ( n ) (( 1 \leq n \leq 50 )), which represents the number of seats at the banquet table.

outputFormat

Output a single integer, the number of seating arrangements possible for the given ( n ) seats.## sample

1

1