Description

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

给定一个字符串 s，F(s) 操作是指将 s 与 s′ 拼接起来，组成新的字符串，其中 s′ 是将 s 的最后一个字符移动到最前面后形成的字符串。

例如，当 s 为 ABCD 时，s′ 为 DABC，拼接而成的新字符串为ABCDDABC。

不断重复 F 操作，可以使得字符串无限延长，每次操作都会使当前字符串的长度加倍。

给定初始字符串和整数 N，请你求出无限延伸的字符串中第 N 个字符是什么。

Input Format

输入共一行，包含一个由大写字母构成的字符串以及一个整数 N。
给定字符串长度不超过 30,1≤N≤1e18。

Output Format

输出由初始字符串构建的无限字符串中的第 N 个字符。

N 从 1 开始计数。

COW 8

C

Hint

题目数据较大，考虑使用long long。

Source

字符串 递归