题目内容

给定一个长度为 n 的字符串 s 和一个长度为 n 的重排表 a。重排表 a 由 1,2,...,n 各出现恰好一次组成。定义一次重排操作：对于每个位置 i（$1 \le i \le n$），新字符串第 i 个字符等于当前字符串第 a_i 个字符。所有位置同时更新，新字符串成为下一次操作的输入。重复执行该操作，求最少需要多少次正整数次操作，才能使字符串恢复到初始状态。由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

约束：

• 字符串 s 的长度 n 满足 $1 \le n \le 2 \times 10^5$。
• s 仅由小写字母组成。
• a_i 满足 $1 \le a_i \le n$，且 1 到 n 每个整数在 a 中出现恰好一次。

输入描述

第一行包含一个整数 n（$1 \le n \le 2 \times 10^5$），表示字符串长度。 第二行包含一个长度为 n 的字符串 s，仅由小写字母组成。 第三行包含 n 个整数 a_1, a_2, \ldots, a_n（$1 \le a_i \le n$），表示重排表。保证这些整数中 1 到 n 每个值恰好出现一次。

输出描述

输出一个整数，表示最少正整数重排次数对 $10^9+7$ 取模后的结果。

样例1

输入

1
a
1

输出

1

说明

排列中只有一个长度为 1 的环。环上字符串为“a”，最小周期 $d=1$。题目要求正整数次操作，因此答案为 1。

样例2

输入

4
abab
2 3 4 1

输出

2

说明

排列 $a=[2,3,4,1]$ 是一个长度为 4 的环。环上字符串为“abab”，它由“ab”重复 2 次组成，因此最小周期 $d=2$。操作 2 次后字符串恢复，而不是 4 次。答案为 2。

样例3

输入

5
ababc
2 1 4 5 3

输出

6

说明

排列分解为两个环：长度 2 的环上字符串为“ab”，周期为 2；长度 3 的环上字符串为“abc”，周期为 3。两个环分别在第 2、3 次操作后恢复，同步恢复需要 $\operatorname{lcm}(2,3)=6$ 次操作。答案为 6。