class Solution {
public:
    int power(int a, int b)
    {
        if(b==0)
        {
            return 1;
        }
        else
        {
            int x=a*power(a,b-1);
            return x;
        }
    }
    int solve(int n, int k)
    {
        if(n==1 && k==1)
        {
            return 0;
        }
        else
        {
            int mid=power(2,n-1)/2;
            if(k<=mid)
            {
                return solve(n-1,k);
            }
            else
            {
                return !solve(n-1,k-mid);
            }
        }
    }
    int kthGrammar(int n, int k) {
      return(solve(n,k));  
    }
};