Ông già Noel với bộ đồ màu đỏ viền trắng, chiếc nón đỏ, chòm râu dài trắng cùng bộ mặt hóm hỉnh và tiếng cười "hô hô hô" đã trở thành biểu tượng của phép nhiệm màu. Trẻ em trên khắp thế giới đều tin rằng, vào đêm Giáng Sinh, ông già Noel sẽ cưỡi một cỗ xe tuần lộc đi khắp thế gian, chui qua ống khói của mỗi ngôi nhà để trao những món quà vào chiếc tất đầu giường khi các em say ngủ. Để rồi sáng hôm sau, các em ai cũng háo hức và bất ngờ vì nhận được những món quà mơ ước trong lá thư các em đã viết gửi ông già Noel.

Năm nay, trường NS tổ chức đón Giáng sinh cho n bạn nhỏ, các bạn nhỏ đứng thành một vòng tròn và cùng nhau tham gia nhiều hoạt động. Hoạt động cuối cùng sẽ là viết thư gửi ông già Noel. Các bạn nhỏ được đánh số từ 1 đến n theo chiều kim đồng hồ (bạn n sẽ đứng cạnh bạn 1), bạn thứ i dự định sẽ viết thư cho ông già Noel với w_i điều ước. Tuy nhiên, các anh chị phụ trách muốn chia n bạn thành một số nhóm, mỗi nhóm gồm một số bạn liên tiếp trên vòng tròn và sẽ cùng nhau viết chung một bức thư gửi ông già Noel. Các nhóm đã thống nhất sẽ ghi một số điều ước vào bức thư chung của nhóm, số điều ước sẽ ghi được tính bằng ước số chung lớn nhất của tất cả các số là số điều ước của từng bạn trong nhóm. Sau khi thu thập được thông tin số điều ước của từng bạn, các anh chị phụ trách muốn chia thành các nhóm mà mỗi nhóm đều có ít nhất là hai điều ước được ghi vào bức thư chung. Một bài toán thú vị để thách đố các bạn nhỏ đó là: Có bao nhiêu cách chia nhóm thỏa mãn, hai cách chia được gọi là khác nhau nếu tồn tại hai bạn nhỏ đứng liên tiếp trên vòng tròn, ở cách này thì cùng một nhóm nhưng trong cách kia thì khác nhóm.

Yêu cầu: Cho w₁,w₂,…,w_n, hãy đếm số cách chia nhóm.

Dữ liệu

Dòng đầu chứa số nguyên dương n;
Dòng thứ hai gồm n số nguyên dương mô tả dãy w₁,w₂,…,w_n  (w_i≤10^9).

Kết quả

Đưa ra một dòng chứa một số nguyên là số lượng cách xếp tìm được chia dư 10^9+7.