← 返回题目列表

AtCoder · kupc2024_j

J. KUPC 接头

中文机器翻译题面 查看原题

配点 : 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