Ami có N ngôi nhà được xếp cạnh nhau trên mặt tiền đường Ngô Quyền. Mỗi ngôi nhà có ai tầng. Một lần đi xem phong thủy cho n ngôi nhà ở thầy bói Huy_Yeu_Minh_Nghia và Zerolifes, Ami phát hiện ra rằng, 2 ngôi nhà là không hợp phong thủy nếu chúng có số tầng khác nhau. Vì thế, Ami quyết định chia N ngôi nhà của mình thành một số dãy. Mỗi dãy gồm một số căn nhà xếp cạnh nhau, sau cho tất cả các ngôi nhà trong 1 dãy đều hợp phong thủy. Bạn hãy cho Ami biết, có bao nhiêu cách chia dãy nhà thỏa mãn điều kiện trên. Vì số cách có thể rất lớn nên các bạn chỉ cần in ra số đó chia dư cho 109+7.
Dữ liệu vào
Dòng đầu là 2 số nguyên dương N (N <= 105) là số ngôi nhà mà Ami sở hữu
Dòng tiếp theo gồm N số nguyên dương a1,a2,a3,…,aN (ai <= 109) lần lượt là số tầng của ngôi nhà thứ i.
Dữ liệu ra
Một số nguyên là số cách chia thỏa mãn sau khi đã chia dư 109 + 7.
Input
5
1 1 2 2 3
Output
4
Input
5
1 2 3 4 5
Output
1
Giải thích
Ở ví dụ 1, có 4 cách chia là
|1| |1| |2| |2| |3|
|1 1| |2| |2| |3|
|1 1| |2 2| |3|
|1| |1| |2 2| |3|.
Ở ví dụ 2 chỉ có một cách chia là mỗi ngôi nhà ở một dãy riêng biệt.