Cho một dãy số ~a_1, a_2, ..., a_n~. Dựa trên dãy này, chúng ta có dược dãy số ~b_1, b_2,.., b_n~, sao cho ~b_i=2^{a_i}~ với mọi ~i~.

Một cách phân đoạn hợp lệ là một cách chia dãy ~b_1, b_2,..,b_n~ thành các đoạn con liên tiếp sao cho mỗi phần tử trong dãy thuộc duy nhất một đoạn. Một cách phân đoạn dược gọi là hoàn hảo nếu như tổng của mỗi đoạn là một lũy thừa của ~2~ (lũy thừa có số mũ nguyên).

Bài toán được đưa ra là đếm số cách phân đoạn dãy ~b_1, b_2,..,b_n~ hoàn hảo. Bởi vì đáp án cho bài toán này rất lớn nên bạn hãy in phần dư của nó khi modulo cho ~10^9 + 7~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \leq n \leq 3 \cdot 10^5~), độ dài của dãy số ~a_1, a_2,...,a_n~ (đồng thời cũng là độ dài của dãy số ~b_1, b_2,...,b_n~).

Dòng tiếp theo gồm ~n~ số nguyên không âm ~a_1, a_2,..., a_n~ (~0 \leq a_i \leq 10^6~).

Output

In ra một dòng duy nhất, là số cách phân đoạn hoàn hảo theo modulo ~10^9 + 7~.

Sample Input 1

5
2 0 0 1 1

Sample Output 1

6

Notes

Trong ví dụ trên, dãy số ~b_1, b_2,...,b_n~ là ~4,1,1,2,2~. Một số cách chia hợp lệ là:

• ~[4], [1], [1], [2], [2]~,

• ~[4], [1, 1], [2], [2]~,

• ~[4], [1], [1], [2, 2]~,

• ~[4], [1, 1], [2, 2]~,

• ~[4], [1, 1, 2], [2]~,

• ~[4, 1, 1, 2], [2]~.