奶牛密码

题目描述

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

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

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

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

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

输入格式

输入共一行，包含一个由大写字母构成的字符串以及一个整数 $N$。

输出格式

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

$N$ 从 $1$ 开始计数。

COW 8

C

提示

#### 数据范围与提示： 给定字符串长度不超过 $30,1≤N≤10^{18}$, 注意，N 可能超过标准的 32 位整数型能够表示的范围，所以你可能需要使用更大的数据类型，例如C/C++中的“long long”。

来源

童程童美