AT_kupc2024_j.Joint for KUPC

给定一个由 K、U、P、C 组成的字符串 $S$。对于正整数 $k$，将 $S$ 连续重复 $k$ 次所得的字符串记为 $S^k$。

考虑由 K、U、P、C 组成的全长为 $L$ 的字符串集合 $U$（$U$ 包含 $4^L$ 个字符串）。
当且仅当 $S^k$ 包含 $U$ 的所有元素作为（可以不连续的）子序列时，求所有可能的 $k$ 的最小值。
如果不存在这样的 $k$，则输出 -1。

输入以以下格式从标准输入中给出。

$S$ $L$

请输出答案。

样例解释 1

在本例中，$S=$ KUPCCPUK，$L=3$。

• $S^1=$ KUPCCPUK，$S^2=$ KUPCCPUKKUPCCPUK，依此类推。
• 在 $S^1$ 中，$U$ 的一些元素，例如 KCC，可以作为子序列出现。
• 例如 UUP 在 $S^1$ 不能作为子序列出现，但在 $S^2$ 中可以作为子序列出现。
• $U$ 的全部 $4^3$ 个元素都能作为子序列出现在 $S^2$ 中。

因此，答案为 $2$。

样例解释 2

在本例中，$S=$ UUUPPPCCC，$L=4$。

KCPC 是 $U$ 的一个元素，但无论多少正整数 $k$，$S^k$ 都无法包含 KCPC 作为子序列。因此，应输出 -1。

数据范围

• $S$ 是由 K、U、P、C 组成，长度在 $1$ 到 $5 \times 10^5$ 之间的字符串。
• $L$ 是满足 $1 \le L \le 10^{18}$ 的整数。

由 ChatGPT 5 翻译