*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/181C1ZLuJW-n0Ln4Y221uAbShnJOAnLIB/view

*Lời giải: * https://drive.google.com/file/d/1IXafO_AxmNyrrDYVg2yeGIzvBKGKP3nh/view

Cho một mê cung gồm n phòng xếp thành 1 hàng, các phòng đánh số từ 1 đến n. Mỗi phòng được mã hóa bằng một số tự nhiên từ 0 đến ~2^{30}-1~. Hải đang ở phòng số 1. Hải có thể di chuyển từ phòng a đến phòng b khi và chỉ khi:

• a < b

• Gọi số mã hóa của phòng a và b lần lượt là x và y. Khi đó phải tồn tại số tự nhiên k để :

  ~ \left \lfloor \frac{x}{2^k} \right \rfloor \quad , \left \lfloor \frac{y}{2^k} \right \rfloor \quad ~ đều là số lẻ.

  ~ \left \lfloor x \right \rfloor \quad ~ : là số x làm tròn xuống. Vd: ~ \left \lfloor 1.6 \right \rfloor \quad ~ = 1

Đồng thời, số cách di chuyển từ phòng a *đến phòng *b bằng số lượng k thỏa mãn yêu cầu trên.

Hải biết rằng mình cần đến được phòng n để thoát khỏi mê cung. Hỏi Hải có bao nhiêu cách để di chuyển từ phòng 1 đến phòng n? Hai cách di chuyển được gọi là khác nhau nếu Hải đi qua một phòng trong một cách nhưng không đi qua trong cách kia, hoặc Hải dùng 2 cách khác nhau để di chuyển giữa hai phòng. Đáp án có thể rất lớn hãy đưa ra đáp án chia dư cho 10^9 + 7.

Input

• Dòng đầu tiên chứa N ~(1 \leq N \leq 10^5)~
• Dòng thứ hai gồm n số nguyên dương không lớn hơn ~10^9~, trong đó số thứ i là số mã hóa của phòng thứ i.

Output

• In ra một số nguyên duy nhất là số cách di chuyển từ phòng 1 đến phòng n, modulo ~10^9 +7~.

Sample Input 1

4
1 3 3 1

Sample Output 1

5

Giải thích đáp án :

Đường đi 1 :
    phòng 1 - 2 : k = 0
    phòng 2 - 3 : k = 0
    phòng 3 - 4 : k = 0

Đường đi 2 :
    phòng 1 - 2 : k = 0
    phòng 2 - 3 : k = 1
    phòng 3 - 4 : k = 0

Đường đi 3 :
    phòng 1 - 4 : k = 0

Đường đi 4 :
    phòng 1 - 2 : k = 0
    phòng 2 - 4 : k = 0

Đường đi 5 :
    phòng 1 - 3 : k = 0
    phòng 3 - 4 : k = 0

Sample Input 2

9
1 3 5 7 9 11 13 15 17

Sample Output 2

732

Task:

• Subtask 1 (10% số test) : ~n \leq 8~
• Subtask 2 (40% số test) : ~n \leq 10^3~
• Subtask 3 (50% số test) : Không ràng buộc gì thêm