奶牛们正在试验密码，并设计了一种方法来创建一个无限长的字符串，作为其密码的一部分。

给定一个字符串s，让F(s)为s，然后s向右“旋转”一个字符(在向右旋转中，s的最后一个字符会旋转并成为新的第一个字符）。给定一个初始字符串s，奶牛通过反复应用F来构建其无限长的代码字符串；因此，每一步都会使当前字符串的长度加倍。

给定初始字符串s和索引n，请帮助奶牛计算无限代码字符串中第n个位置的字符。

输入由一行组成，其中包含一个字符串s和n。该字符串最多由30个大写字符组成，n≤10^18。

请注意，N可能太大，无法适应标准的32位整数，因此您可能希望使用64位整数类型（例如，C/C++中的“long long”）。

COW -> COWWCO -> COWWCOOCOWWC
                 12345678