Tèo đang bị lạc trong mê cung và cần tìm đường thoát ra. Mê cung gồm \(n\) 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\).

Tèo đang ở phòng số 1. Trong phòng này có hướng dẫn rằng Tèo 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 đó tồn tại số tự nhiên \(k\) để: \(\left \lfloor \frac{x}{2^k} \right \rfloor, \left \lfloor \frac{y}{2^k} \right \rfloor\) đều là số lẻ.

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

Tèo biết bằng mình cần đến được phòng \(n\) để thoát ra khỏi mê cung. Hỏi Tèo có bao nhiêu cách
để di chuyển từ phòng 1 đến phòng \(n\)? Hai cách di chuyển được coi là khác nhau nếu Tèo đi qua
một phòng trong một cách nhưng không đi qua trong cách kia, hoặc Tèo dùng 2 cách khác nhau
để di chuyển giữa hai phòng. Đồng thời, vì đáp án có thể rất lớn, chỉ cần đưa ra đáp án \(modulo\)
\(10^9 + 7\).

Input

• Dòng đầu tiên gồm một số nguyên \(n\) là số phòng trong mê cung (\(1 \le n \le 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à 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\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 8\)
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^3\)
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 3 3 1

5

9
1 3 5 7 9 11 13 15 17

732