Justin is lost in a maze and needs to find a way out. The maze consists of n rooms numbered from 1 to n. Each room is encoded with a natural number from 0 to 2^{30}-1.

Justin is currently in room 1. In this room, there are instructions that Justin can move from room a to room b if and only if:

• a < b
• Let the room codes of a and b be x and y, respectively. Then, there exists a natural number k such that \lfloor \frac{x}{2^k}, \frac{y}{2^k} \rfloor are all odd.

At the same time, the number of ways Justin moves from room a to room b is equal to the number of natural numbers k that satisfy the above requirement. Justin knows that he needs to reach room n to escape the maze.

How many ways are there for Justin to move from room 1 to room n? Two ways are considered different if Justin passes through a room in one way but not in the other, or if Justin uses two different ways to move between two rooms. Additionally, because the answer can be very large, only give the answer modulo 10^9+7.

• The first line contains an integer n, the number of rooms in the maze (1 \leq n \leq 10^5).
• The second line contains n positive integers not greater than 10^9, where the i^{th} number is the code of the i^{th} room.

Print a single integer which is the number of ways for Justin to move from room 1 to room n modulo 10^9+7

• Subtask 1 (10% of the test cases): n \leq 8
• Subtask 2 (40% of the test cases): n \leq 10^3
• Subtask 3 (50% of the test cases): No additional constraints.