Deploying Knights in Castles

You are given a single integer (n) representing the number of castles arranged in a line. Your task is to determine the number of distinct ways to deploy knights in these castles such that no two knights are adjacent. A castle can either have a knight or be empty. Note that when (n = 0), there is exactly 1 way (doing nothing).

This problem can be solved using dynamic programming. Let (dp[i]) denote the number of valid deployment configurations for the first (i) castles. Then, the following recurrence relation holds: [ dp[i] = dp[i-1] + dp[i-2] ] with base cases: [ dp[0] = 1, \quad dp[1] = 2. ]

The answer for a given (n) is (dp[n]).

inputFormat

The input consists of a single line containing one integer (n) (where (0 \leq n \leq 10^5)) – the number of castles.

outputFormat

Output a single integer which is the number of distinct ways to deploy the knights under the constraint that no two knights are adjacent.## sample

1

2