The Non-Repeating Climber

You are climbing a staircase with N steps. You can take 1, 2, or 3 steps at a time. However, to keep the climb interesting, you are not allowed to take the same number of steps twice in a row (e.g., if you just took 2 steps, your next jump must be 1 or 3). How many distinct ways can you reach the top (exactly step N)? Input Format: A single integer N. Output Format: A single integer representing the number of valid paths. Example: Input: 4 Output: 3 (Paths: [1, 2, 1], [1, 3], [3, 1])