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ó a_i 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. Lưu ý rằng, ngôi nhà có số tầng bằng 0 là hợp phong thủy với mọi ngôi nhà.

Dữ liệu vào

Dòng đầu là 2 số nguyên dương N (N <= 10⁵) là số ngôi nhà mà Ami sở hữu

Dòng tiếp theo gồm N số nguyên không âm a₁,a₂,a₃,…,a_N (a_i <= 2*10⁵) 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 chia dư cho 10⁹+7.