配点 : 100 点
問題文
K, U, P, C 由……组成的字符串 S 。正整数
关于 k ,这
连续排列 S 被 k 次的字符串
它被称为 S^k 。
由
长度
有一个 L 的 K, U, P, C 组成的所有字符串的集合
考虑 U (
由 U 为 4^L 字符串组成)。
当包含
S^k 被给予 U 的所有元素作为子序列(不必是连续的)时,
求 k 的最小可能值。
然而,这样
如果 k 不存在,则使用
长度由 -1 。
制約
- S 为
K,U,P,C组成 满足 1 以上 5 \times 10^5 以下字符串 - L 为 1 \le L \le 10^{18} 的整数
入力
输入将以以下格式从标准输入给出。
S L
出力
打印答案。 它是按此顺序连接的
入力例 1
KUPCCPUK 3
出力例 1
2
通过此输入, S= KUPCCPUK 、 L=3 。
- S^1=
KUPCCPUK、 S^2=KUPCCPUKKUPCCPUK、 \dots 。 - U 的元素中,例如
作为子序列包含在
KCC为 S^1 中。 - U 的元素中,例如
作为子序列包含在
UUP为 S^1 不作为子序列包含在内,但 S^2 作为子序列包含在内。 所有 - U 的 4^3 元素都是 S^2 中。
由上可知,答案是 是 2 。
入力例 2
UUUPPPCCC 4
出力例 2
-1
通过此输入, S= UUUPPPCCC 、 L=4 。
KCPC 为 U 的元素,但任意正整数
关于 k ,
它从不包含 S^k 被给予 KCPC 作为子序列。因此,
输出 -1 。
入力例 3
PPCPCPKCPCPUUUUPKPCPKCPKUPCCKPPCPUKUPPPUPPUKUUKUUKPKPKPCUKKKUKUKUCPCCPUUUKCUPPCCKKKKCU 1000000000000000000
出力例 3
111111111111111112