Description

Huang Xiaoming and his partner want to start an English training institute. When registering, they need to fill out a personal information form, and Xiaoming is troubled by the height field.

The height must be accurate to centimeters, but Xiaoming is so tall that such a long number cannot fit on the paper. He bribed the staff, so he only needs to write the result of his height modulo $10007$.

However, Xiaoming does not know how to take a modulus. Remembering that you helped him solve the reservoir problem a few days ago, he came to you again for help.

Input Format

Xiaoming’s height is represented as $a_1^{a_2^{\cdots^{a_n}}}$. The first line contains $n$, and the second line contains $n$ positive integers representing $a_1$ to $a_n$.

Output Format

Output a single number representing Xiaoming’s height $\bmod 10007$.

2										
17 747

173

Hint

All $0 \le a_i < 10^4$.

For testdata 1–6, $n = 2$.

For testdata 7–10, $n = 3$.

For testdata 11, $n = 1234567$.

Translated by ChatGPT 5