Count Valid Sequences

Given an integer T, count the number of distinct valid sequences that can be generated starting from 1, where each subsequent number is obtained by adding either 1 or 2 to the previous number. A sequence is considered valid if its maximum element does not exceed T.

The problem can be modeled using the recurrence relation \[ dp[i] = dp[i-1] + dp[i-2], \] with the initial conditions \[ dp[1] = 1 \quad \text{and} \quad dp[2] = 2 \quad (\text{for } T \ge 2). \]

For example, if T = 5, the valid sequences are generated as follows: starting with 1, you can reach 2 (by +1) or 3 (by +2), and so on. Hence, the total number of valid sequences for T = 5 is 8.

inputFormat

Input: A single line containing an integer T (1 ≤ T ≤ 10ⁿ for some appropriate bound), which represents the maximum allowed value in the sequence.

The input is read from stdin.

outputFormat

Output: Print a single integer that represents the number of valid sequences which can be formed under the given conditions. The output should be written to stdout.

1

1