409791: GYM103743 H Super Gray Pony

Ponyville is on its annual math festival! The ponies who are able to overcome this problem would be honored as $$$\text{Super Gray Pony}$$$. Get yourself prepared for the problem and try your best!

In this problem, the $$$i$$$-order Gray Code is defined recursively as $$$a^{(i)}$$$ - an array of binary numbers with $$$2^i$$$ elements numbered from $$$0$$$ to $$$2^i-1$$$. Note that in this problem leading zeros are added to make each element a strictly $$$i$$$-bit binary number. The specific rules are as follows:

1. For $$$i = 1$$$, $$$a^{(1)}=[0,1]$$$, $$$a^{(1)}[0]=0$$$, $$$a^{(1)}[1]=1$$$.
2. For $$$i > 1$$$, the first half of $$$a^{(i)}$$$ $$$(a^{(i)}[0], ..., a^{(i)}[2^{i - 1} - 1])$$$ can be obtained by adding a digit $$$0$$$ in front of the highest bit of each element in $$$a^{(i-1)}$$$.
3. For $$$i > 1$$$, the second half of $$$a^{(i)}$$$ $$$(a^{(i)}[2^{i - 1}], ..., a^{(i)}[2^{i} - 1])$$$ can be obtained by adding a digit $$$1$$$ in front of the highest bit of each element in $$$a^{(i-1)}$$$ and then arrange these elements in a reversed order.

For example:

• $$$a^{(1)}=[0,1]$$$
• $$$a^{(2)}=[00, 01] + \text{rev}([10, 11])=[00, 01, 11, 10]$$$
• $$$a^{(3)}=[000, 001, 011, 010] + \text{rev}([100, 101, 111, 110])=[000, 001, 011, 010, 110, 111, 101, 100]$$$

Given $$$S$$$ and $$$k$$$, $$$S_k$$$ is defined as:

$$$$$$ S_k=\underbrace{a^{(n)}[a^{(n)}[\ldots a^{(n)}}_{k \times a^{(n)}}\ldots ]] $$$$$$

Now given $$$S$$$ and $$$k$$$, you need to calculate the exact value of $$$S_k$$$. In this problem, $$$S$$$ is given in the form of an $$$n$$$-bit binary number, possibly with leading zeros.

3 5
011

010