Binary Strings Without Consecutive Ones

Given an integer \(n\), count the number of unique binary strings of length \(n\) such that no two consecutive '1's appear. This problem can be modeled using a recurrence relation similar to the Fibonacci sequence. Specifically, let \(dp[n]\) be the number of valid binary strings of length \(n\). Then the recurrence is given by:

$$dp[n] = dp[n-1] + dp[n-2]$$

with base cases \(dp[1] = 2\) (which corresponds to the strings "0" and "1") and \(dp[2] = 3\) (which corresponds to "00", "01", "10"). For example, when \(n = 3\), the answer is \(5\), since the valid strings are: "000", "001", "010", "100", and "101".

inputFormat

The input consists of a single integer \(n\) (where \(n \ge 1\)).

outputFormat

Output a single integer representing the number of unique binary strings of length \(n\) that do not contain any adjacent '1's.

## sample

1

2