ZZULIOJ

题目描述

小

Z

有一个序列a长度为n，其中所有

a i

满足

(1 \leq a i \leq n)

且互不相等。
小

Z

通过这个序列构造了一个n个点的有向图，方式是对于所有的点i，由i向

a_{i}

连一条有向边。
现在在这个有向图里每个点都被赋予了一个权值

b i (0 \leq b i \leq 9)

，如果在图上行走，经过的点的权值依次排列会组成一个十进制数字，有可能出现有前导0的情况，此时我们忽略前导0。
小

Z

想知道，在图上任意点开始行走任意步数，所能构成的数字对

109

取模的最大值是多少？

输入

第一行输入一个n $(1 \leq n \leq 2 * 105)$ ，表示序列的长度
第二行n个整数用空格隔开，表示序列a,第i个数表示 $a i (1 \leq a i \leq n)$ 且互不相等
第三行n个整数用空格隔开，表示序列b,第i个数表示 $b i (0 \leq b i \leq 9)$

输出

输出一行一个整数，表示答案。

样例输入 Copy

5
2 3 4 5 1
1 2 3 4 5

样例输出 Copy

512345123

来源/分类

“卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛

3033: 最大的数