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 翻译