Count how many ways to reach exactly stairs using steps of size 1 or 2, with an additional parity-style constraint from the original Codeforces formulation.
You are given a positive integer . Consider all sequences of moves that climb exactly stairs, where each move is either 1 stair or 2 stairs.
Count how many different sequences are valid under the problem’s constraint from the original statement. The answer depends on how many 2-step moves are used, and only certain combinations are allowed.
Your task is to compute and print the number of valid sequences.
Input Format
A single integer .
Output Format
Print one integer — the number of valid sequences.
Constraints
- Use 64-bit integer arithmetic where needed.
Example 1
Input
4
Output
5
Explanation
Valid ways to climb 4 stairs with 1- and 2-step moves are: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.
Example 2
Input
3
Output
3
Explanation
The valid sequences are 1+1+1, 1+2, and 2+1.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.