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 để:

đề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 ≤ n ≤ ~ 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.

Sample

Input #1

4
1 3 3 1

Output #1

5

Input #2

9
1 3 5 7 9 11 13 15 17

Output #2

732

Problem source: Testing Round 16