After discovering the famous totient function 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 . Since he was playing with totient function he immediately applied totient function to and got a new number . But the number was still very large so he again applied totient to it and got another number 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 . Euler solved it in the dream. Can you do it too?
and where is an integer and
Find smallest such that
Note: Euler totient function of a positive integer is defined as the number of positive integers less than or equal to such that
First line of input contains an integer
Next line contains prime numbers
Next line contains integers
For each ,
It is guaranteed that each is pairwise distinct.
For each ,
Then the input number is calculated as
Print the smallest positive such that
Since can be very large, output it modulo
2 3 2 1 1
1 11 1