Untitled

public class Solution {
    HashMap<Long, Long> hm = new HashMap<>();
    int mod = (int)(1e9+7);
    
    public long fastPow(int a, long n){
        if(n == 0){
            return 1;
        }

        long res = fastPow(a, n/2) % mod;

        if(n % 2 == 0){
            return (res*res) % mod;
        }
        else{
            return (((res * res) % mod) * a) % mod;
        }
    }

    private long nCr(long n, long r) {
        if (r > n) {
            return 0;
        }
        if (r == 0 || n == r) {
            return 1;
        }

        if (hm.containsKey(n * mod + r)) {
            return hm.get(n * mod + r);
        }

        long result = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % mod;
        hm.put(n * mod + r, result);
        return result;
    }

    public long findWays(long n){
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }

        if(hm.containsKey(n)){
            return hm.get(n);
        }
        
        //h is the second last level of the tree as the elements are completely filled till 2nd last level
        //the above is the property of complete binary tree
        long h = (long)(Math.log(n) / Math.log(2));
        long x = ((long)fastPow(2, h) - 1) % mod;

        long leftCount = ((long)x-1)/2;
        leftCount = (leftCount + Math.min(n - x, ((long)x+1)/2)) % mod;

        long rightCount = ((long)n - 1 - leftCount) % mod;

        long ways = (nCr(n-1, leftCount)) % mod;
        hm.put(n, (long)((((ways * findWays(leftCount)) % mod) * findWays(rightCount)) % mod));

        return hm.get(n);
    }

    public int solve(int A) {
        return (int)(findWays(A) % mod);
    }
}