题目内容

报文流水线按固定置换反复重排字符串。给定长度为 $n$ 的字符串 $u$，以及长度为 $n$ 的排列 $p$（下标从 $1$ 开始）。一次操作生成等长新串 $w$：对每个位置 $i$（$1 \le i \le n$）有 $w_i = u_{p_i}$，再令 $u = w$。无限重复该操作，求最少的正整数次数 $k$，使字符串回到最初形态；输出 $k \bmod (10^9+7)$。

长度为 $n$ 的排列：由 $1,2,\dots,n$ 各出现恰好一次构成的序列。例如 $\{3,1,4,2\}$ 是长度为 $4$ 的排列；而 $\{2,2,1,3\}$ 不是（元素 $2$ 出现两次，$4$ 未出现），$\{1,2,3,5\}$ 也不是（出现了超出 $[1,4]$ 范围的 $5$）。

输入描述

第一行一个整型 $n$ $(1 \le n \le 2\times 10^5)$。

第二行一个长度为 $n$、仅含小写字母的字符串 $u$。

第三行 $n$ 个整型，给出排列 $p$ $(1 \le p_i \le n)$。

输出描述

新起一行写出一个非负整型，即最少操作次数对 $10^9+7$ 取模后的结果。

样例1

输入

2
xy
2 1

输出

2

说明

排列形成循环 $1\to 2\to 1$。操作一次得到 yx，再操作一次回到 xy，故 $k=2$。

样例2

输入

3
zzz
2 3 1

输出

1

说明

排列为循环 $1\to 2\to 3\to 1$，但三位字母相同，操作一次后仍为 zzz，故 $k=1$。

样例3

输入

5
hello
2 3 4 5 1

输出

5

说明

排列为单一循环 $1\to 2\to 3\to 4\to 5\to 1$，字符串五位在循环上两两不同，需操作 $5$ 次才回到 hello。