ストーリー

単換字式暗号とは、ある文字を別の文字に一対一対応させることで暗号化する暗号方式です。

例えば k → y, i → a, w → m と対応させると kiwi が yama になります。

高橋くんは、どんな文章に対しても、この暗号を繰返し適用すると、ある時もとに戻ることに気が付きました。

問題文

正整数 $N$ と、 $(1, 2, \ldots, N)$ の順列 $(P_1, P_2, \ldots, P_N)$ が与えられます。

この順列の意味は、暗号化を、 $i$ 番目の記号を $P_i$ 番目の記号で置き換えることによって行うというものです。

正整数 $M$ と、文章を表す数列 $(S_1, S_2, \ldots, S_M)$ が与えられます。

与えられた文章に対し、この暗号を $1$ 回以上繰返し適用するとき、最小で何回適用すると元に戻るか求めてください。

ただし、答えは非常に大きくなることがあるので、答えを $10^9 + 7$ で割ったあまりを出力してください。

制約

• $1 \le N, M \le 10^5$
• $1 \le P_i, S_i \le N$
• $P$ は $(1, 2, \ldots, N)$ の順列である
• 入力はすべて整数である

入力

出力

答えを $10^9 + 7$ で割ったあまりを出力せよ。

入出力例

5 4
4 1 2 5 3
1 2 3 4

5

1 2 3 4 → 4 1 2 5 → 5 4 1 3 → 3 5 4 2 → 2 3 5 1 → 1 2 3 4 となり、 $5$ 回の暗号化で元に戻ります。

9 5
1 4 2 3 9 7 6 8 5
9 2 6 3 4

6

$6$ 回の暗号化で元に戻ります。

120 9
41 73 33 39 6 99 114 57 59 21 76 47 106 67 29 64 111 120 66 116 80 115 78 98 13 31 37 93 56 86 44 81 104 19 60 45 53 9 42 12 10 54 55 18 11 74 16 25 46 8 4 92 43 7 28 49 100 52 83 23 89 51 38 112 24 30 119 50 77 88 65 107 113 90 102 79 3 72 36 87 85 35 108 40 58 84 103 15 22 61 94 118 91 101 32 105 17 97 5 26 62 68 14 34 110 48 82 69 27 1 95 63 96 109 2 71 75 20 70 117
13 6 45 82 102 32 93 47 88

176307853

$10^9 + 7$ で割ったあまりを出力することに注意してください。