Các bạn học sinh tại trường tiểu học L làm bài quá nhanh chóng, hiện tại đang đòi một bài tập thử thách hơn. Nên tôi bảo các bạn ấy tính cái này. Cho số \(X = (\cdots ((a_1^{a_2})^{a_3})^{a_4} \cdots )^{a_n}\). Sau khi đem \(X\) chia lấy dư cho \(2004010501\) thì được kết quả là bao nhiêu?.

Nói cách khác, bạn được cho dãy \(a\) gồm \(n\) số nguyên dương lớn hơn \(1\). Bạn lấy số thứ nhất lũy thừa cho số thứ hai, xong lại lấy kết quả đem đi lũy thừa cho số thứ ba, rồi lại lấy kết quả đem đi lũy thừa cho số thứ tư, ..., cứ như thế cho tới số cuối cùng.

Ơ nhưng đây là bài tập của mấy bạn ấy mà, sao các bạn lại phải code nhỉ? Dù sao cũng lỡ rồi nên các bạn cứ làm đi nhé.

Input

• Dòng đầu chứa số \(n\), \(1 \le n \le 10^6\).
• Dòng tiếp chứa \(n\) số nguyên dương, trong đó \(1 < a_i \le 10^{18}\)

Output

• Gồm một dòng duy nhất chứa kết quả

Example