Hash happens to be a very smart dog. He recently read about fibonacci numbers. His master has given him a relation similar to fibonacci recurrence as follows,
f(n) = 5 f(n-1) + 3 f(n-2) for n > 1 and f(0) = f(1) = 1 Rather than giving him the k^th number of the sequence to compute, his master has given him N numbers whose product is k and asked him to calculate the last 3 digits of f(k).

Hash is very confused so he asks your help to solve it. Help Hash to get the answer.

Input Format:

The first line of the input contains a single integer denoting N. (N<= 10⁶). The second line contains N space seperated integers (<=10¹⁸).

Output Format:

Print the last 3-digit of f(k).