Binary Expansion Bit at Index

You are given a binary string s, an integer k, and a 0-based position index.

One expansion step rewrites the string by replacing every 0 with 00 and every 1 with 10, so the string doubles in length. After k expansion steps the string has length s.length * 2^k, far too long to build.

Return the bit (0 or 1) at position index of the string after k expansion steps.

Examples

Example 1

Input: s = "01", k = 1, index = 2
Output: 1
Explanation: One step turns "01" into "0010"; position 2 holds 1.

Example 2

Input: s = "1", k = 2, index = 1
Output: 0
Explanation: "1" -> "10" -> "1000"; position 1 holds 0.

Example 3

Input: s = "101", k = 0, index = 2
Output: 1
Explanation: With no steps the string is unchanged.