Bạn được cho một mảng ~a~ gồm ~n~ số nguyên dương, mỗi phần tử ban đầu được bọc trong một "phản tế bào". Mỗi phản tế bào có thế chứa nhiều phần tử liên tiếp nhau, tuy nhiên theo định nghĩa trên thì ban đầu mỗi phản tế bào chỉ chứa một phần tử. Trái với việc phân chia của một tế bào thành hai tế bào con giống nhau, hai phản tế bào cạnh nhau có thể ghép lại thành một phản tế bào lớn hơn với toàn bộ phần tử từ hai phản tế bào này nếu tổng các phần tử trong hai phản tế bào này là như nhau.

Bạn cũng nhận được một dãy ~b~ rỗng, và một số nguyên dương ~i~ được gán bằng ~1~. Nhiệm vụ của bạn là thay đổi dãy ~b~ sử dụng các thao tác sau:

• Nếu ~i = n + 1~, dừng thao tác thay đổi dãy ~b~.
• Xét phản tế bào đang chứa phần tử ~a_i~ (gọi là ~X~), và phản tế bào liền kề trước ~X~ (gọi là ~Y~). Bạn được quyền lựa chọn việc ghép ~X~ và ~Y~ nếu như ~Y~ tồn tại và tổng các phần tử trong ~X~ bằng tổng các phần tử trong ~Y~. Lưu ý là nếu cả hai điều kiện là hợp lệ, bạn có thể chọn ghép hoặc không ghép hai phản tế bào này.
• Nếu bạn chọn không ghép (hoặc bạn không thể ghép) ~X~ và ~Y~, tăng ~i~ lên ~1~.
• Nếu bạn chọn ghép ~X~ và ~Y~, ghép hai phản tế bào lại và thêm ~i~ vào đuôi của ~b~. Lưu ý ta không tăng ~i~ nếu chọn ghép.

Ta có thể chứng minh thao tác trên sẽ luôn kết thúc (tức sau hữu hạn bước ta sẽ có ~i = n + 1~). Bạn cần đếm có bao nhiêu dãy ~b~ khác nhau có thể tạo được sử dụng các thao tác này. Hai dãy ~c~ và ~d~ khác nhau nếu ~|c| \ne |d|~ hoặc tồn tại một vị trí ~i~ sao cho ~c_i \ne d_i~.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~) - số lượng phần tử trong ~a~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, a_3, \dots, a_n~ (~1 \le a_i \le 10^9~) - các phần tử trong ~a~.

Output

Ghi ra số lượng dãy ~b~ khác nhau có thể tạo được từ các thao tác đã cho. Vì số lượng dãy ~b~ có thể rất lớn, ghi ra con số này dưới modulo ~10^9 + 7~.

Sample Input

4
1 1 1 1

Sample Output

6

Subtask

• ~20\%~ số test có ~n \le 20~
• ~80\%~ số test còn lại không có điều kiện gì thêm

Note

Một ví dụ về dãy ~b~ có thể tạo được như sau. Các phản tế bào sẽ được đánh nhau bằng các phần tử giữa ngoặc vuông.

• ~a = [1][1][1][1]~, ~i=1~, ~b=[]~, không thể ghép vì không tồn tại ~Y~.
• ~a = [1][1][1][1]~, ~i=2~, ~b=[]~, chọn ghép hai phản tế bào ~[1]~ và ~[1]~.
• ~a = [1, 1][1][1]~, ~i=2~, ~b=[2]~, không thể ghép vì không tồn tại ~Y~.
• ~a = [1, 1][1][1]~, ~i=3~, ~b=[2]~, không thể ghép vì ~[1, 1]~ và ~[1]~ không cùng tổng.
• ~a = [1, 1][1][1]~, ~i=4~, ~b=[2]~, chọn ghép hai phản tế bào ~[1]~ và ~[1]~.
• ~a = [1, 1][1, 1]~, ~i=4~, ~b=[2, 4]~, chọn không ghép hai phản tế bào ~[1, 1]~ và ~[1, 1]~.
• ~a = [1, 1][1, 1]~, ~i=5~, ~b=[2, 4]~, kết thúc thao tác. Dãy ~b~ cuối cùng là ~[2, 4]~.