Start with the string S1 = "0". For each following string, concatenate the previous string, a single 1, and a reversed copy of the previous string with every bit flipped. Flipping exchanges 0 and 1. Return the bit at position k of Sn as a one-character string. Positions start at 1.
Example 1:
Input: n = 2
k = 3
Output: "1"Explanation: S2 is 011. Its third bit is 1.
Example 2:
Input: n = 3
k = 5
Output: "0"Explanation: S3 is 0111001. Counting positions from 1, the fifth bit is 0.
Example 3:
Input: n = 4
k = 8
Output: "1"Explanation: S4 is 011100110110001. The eighth position is its middle bit, which is 1.
Constraints:
1 <= n <= 201 <= k <= 2^n - 1