AT_kupc2024_j Joint for KUPC

`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 $ $ L $

答えを出力せよ。

### Sample Explanation 1 この入力では、 $ 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 $ です。 ### Sample Explanation 2 この入力では、 $ S= $ `UUUPPPCCC` 、 $ L=4 $ です。 `KCPC` は $ U $ の要素ですが、どのような正整数 $ k $ についても、 $ S^k $ が `KCPC` を部分列として含むことはありません。よって、 `-1` と出力します。 ### Constraints - $ S $ は `K`, `U`, `P`, `C` からなる長さ $ 1 $ 以上 $ 5 \times 10^5 $ 以下の文字列 - $ L $ は $ 1 \le L \le 10^{18} $ を満たす整数