```
class Solution {
public:
int climbStairs(int n) {
if(n <= 3) return n;
int maxTwos = n /2;
int result = 1;
int prev = n -1;
result += n-1;
for(int i=2; i<= maxTwos; i++){
long long lastTwos = i-1;
long long lastOnes = n - (2* (i-1));
int current = prev * (lastOnes * (lastOnes-1))/((lastTwos + lastOnes)*(lastTwos +1));
result += current;
prev = current;
}
return result;
}
};
```