Counting Ways to Reach a Distance

You are given a positive integer D which represents a distance. You can take either a step of 1 unit or a step of 2 units at a time. Your task is to determine the number of distinct ways to exactly reach the distance D.

The solution is based on the recurrence relation:

\(dp(D)=dp(D-1)+dp(D-2)\)

with the base cases defined as:

• \(dp(1)=1\)
• \(dp(2)=2\)

Implement your solution such that it reads the input from stdin and prints the result to stdout.

inputFormat

The input consists of a single line containing an integer D (representing the distance). You can assume D \(\ge 1\).

outputFormat

Output a single integer which is the number of distinct ways to reach the distance D.

1

1