問題文

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} を満たす整数

入力例 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