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.
