class Solution {
    public int kthGrammar(int N, int K) {
       int f[][] = new int[N][(int) Math.pow(2, N - 1)];
		for (int j = 1; j < N; j++) {
			int k = 0;
			int limit = (int) Math.pow(2, j);
			for (int i = 0; i < limit; i += 2) {
				if (f[j - 1][k] == 0) {
					f[j][i] = 0;
					f[j][i + 1] = 1;
					k++;
				} else if (f[j - 1][k] == 1) {
					f[j][i] = 1;
					f[j][i + 1] = 0;
					k++;
				}
			}
		}

		return f[N-1][K - 1];
 
    }
}