Công ty IUHCoder tuy có các thành viên không cùng lớp, cùng Khoa nhưng lại rất đoàn kết và hoạt động rất chăm chỉ. Mỗi người trong cty có một năng lượng tích cực, được cho bởi một số nguyên. Năng lượng tích cực của một nhóm sẽ bằng năng lượng tích cực của những người trong nhóm đó nhân lại với nhau. Vì sự đoàn kết nên có không quá một thành viên có năng lượng tích cực bị âm thôi, còn lại thì đều là các số không âm. Mỗi buổi họp của cty, các thành viên sẽ ngồi vào một dãy bàn và CEO Tina sẽ cùng bàn bạc các kế hoạch chiến lược. Tuy nhiên, gần đây có một số task bị chậm trễ tiến độ. Vì thế CEO muốn chọn ra một nhóm các bạn ngồi liên tiếp trong dãy bàn (nhóm này có ít nhất một người) mà giá trị năng lượng tích cực của nhóm đó là nhỏ nhất. CEO muốn làm việc riêng với các bạn này, tìm hiểu nguyên nhân xem thế nào. Hãy giúp CEO tính ra giá trị nhỏ nhất đó nhé.

Input

Dòng đầu tiên gồm số ~n~ cho biết số thành viên của công ty, trong đó ~1 \le n \le 10^5~. Dòng tiếp theo cho biết năng lượng tích cực của mỗi người, là các số nguyên có giá trị tuyệt đối không quá ~10^6.~

Output

Đáp số của bài toán, lấy số dư khi chia cho ~10^9+7~, số dư này sẽ nằm trong khoảng giá trị ~0,1,...,10^9+6.~

Sample input 1:

3
1 2 3

Sample output 1:

1

Sample input 2:

3
0 2 3

Sample output 2:

0

Sample input 3:

3
-1 2 3

Sample output 3:

1000000001

Giải thích: giá trị nhỏ nhất trong VD1 và VD2 là dễ thấy, còn trong VD3, ta thấy nếu lấy tích cả ba năng lượng tích cực thì ra được ~-6~, số dư cần tìm sẽ là ~10^9+1.~