```
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
lst1 = []
lst2 = []
s = 0
if n%2 == 0:
l = n/2
for i in range(l):
p = 1
q = 1
for j in range(i+1):
p = p*(n-i-j-1)
q = q*(j+1)
lst1.append(p/q)
for k in range(len(lst1)):
s += lst1[k]
return (s+1)
if n%2 == 1:
l = (n-1)/2
for i in range(l):
p = 1
q = 1
for j in range(i+1):
p = p*(n-i-j-1)
q = q*(j+1)
lst2.append(p/q)
for k in range(len(lst2)):
s += lst2[k]
return (s+1)
```