Limits 1s, 512 MB

After discovering the famous totient function ϕ(x)\phi(x) Euler got so fond of it that he applied it to every number he could find on his table. He played all day with this newly discovered function. Then he went to sleep. He was dreaming about the function too.

In the dream, he found a very big number xx. Since he was playing with totient function he immediately applied totient function to xx and got a new number ϕ(x)\phi(x). But the number was still very large so he again applied totient to it and got another number ϕ(ϕ(x))\phi(\phi(x)) which was still way too big. As a result, Euler got frustrated. He wondered how many times he had to apply totient function before reaching 11. Euler solved it in the dream. Can you do it too?

Formally, let y0=xy_0 = x

and yn=ϕ(yn1)y_n = \phi(y_{n-1}) where nn is an integer and n1n\ge 1

Find smallest nn such that yn=1y_n = 1

Note: Euler totient function of a positive integer nn is defined as the number of positive integers ii less than or equal to nn such that gcd(n,i)=1gcd(n,i) = 1

Input

First line of input contains an integer k(1k105)k ( 1\le k \le 10^5)

Next line contains kk prime numbers p1,p2,pkp_1, p_2, … p_k

Next line contains kk integers e1,e2,eke_1,e_2,…e_k

For each 1ik1\le i\le k , 2pi1062 \le p_i \le 10^6

It is guaranteed that each pip_i is pairwise distinct.

For each 1ik1\le i\le k , 1ei1061 \le e_i \le 10^6

Then the input number is calculated as x=i=1kpieix =\prod_{i = 1}^{k}p_i^{e_i}

Output

Print the smallest positive nn such that yn=1y_n = 1

Since nn can be very large, output it modulo 998244353998244353

Samples

InputOutput
2
3 2
1 1
2
InputOutput
1
11
1
4

Submit

Login to submit.

Statistics

77% Solution Ratio
kawchar85Earliest, 8M ago
KnightshadeFastest, 0.0s
NiloyDas19Lightest, 7.5 MB
kotoshogiku.510125Shortest, 923B
Toph uses cookies. By continuing you agree to our Cookie Policy.