Untitled

class Solution {
public:
    int waysToReachStair(int k) {
        map<array<long long,3>,int> dp;
        const long long bound=1000000000;
        function<int(long long,int,int)> rec=[&](long long curr,int jump,int flag){
            if(curr>bound) return 0;
            if(dp.find({curr,jump,flag})!=dp.end()) return dp[{curr,jump,flag}];
            int ans=0;
            if(!flag and curr>0){
                ans+=rec(curr-1,jump,1);
            }
            ans+=rec(curr+(1LL<<jump),jump+1,0);
            return dp[{curr,jump,flag}]=ans+(curr==k);
        };
        return rec(1,0,0);
    }
};