Cho mảng ~A~ có ~N~ phần tử. Tính phần dư của phép chia tích các phần tử trong dãy ~A~ đó với ~10^9+7~.

Input

• Gồm một dòng duy nhất chứa ~N+1~ số nguyên, có giá trị từ ~1~ tới ~10^7~, bao gồm các số ~N\ (1 \le N \le 10^5),\ A_1,\ A_2,\ \dots~

Output

• Đáp án của bài toán.

Sample Input 1

3 17 70 13

Sample Output 1

15470