Cho 1 loạt các số trong 1 dãy số,S là tích của tất cả các số trong dãy số này. Bạn hãy tìm số dư khi chia S cho 10^9 + 7.

Input Format

Dòng đầu tiên là N : số lượng số trong dãy số.(1<=N<=1000) Dòng thứ 2 là N số trong dãy số.(Các số trong dãy là số không âm không vượt quá 10^10)

Constraints

.

Output Format

In ra kết quả của bài toán.

Ví dụ:

Dữ liệu vào

6
4 8 2 3 4 5

Dữ liệu ra

3840