Limits
1s, 512 MB

Abir is a school going boy, who loves math. Also, he loves to play with stones. Recently he invented a game.

Abir has infinite amount of stones. He takes **N** of them and arranges them in a **circle**. He marks them using numbers **1, 2, 3,... N**. Stone 2 is next to stone number 1. And so on. As the stones are arranged in a circle, after the stone number **N** there is the first stone with stone number 1. He calls this the Circle of Death.

Now he takes out every **second** stone from the circle of death until there is only one stone left in the circle. For example, if he starts with 5 stones, he takes out the stones in the following order: First he skips the 1st stone and throws out the 2nd stone. Then he skips the 3rd stone and he throws out 4th stone. Then he skips the 5th stone and throws out the 1st stone. After this process, the only stone that was not thrown out is the stone number 3. Then he arranges another circle of death with 3 stones (as 3 was the number of only stone that was left in the last circle). And he again identifies the stone as 1, 2 and 3. Then he again throws away every second stone from the circle of death. The throwing process happens as this: 2 -> 1. And again 3 is the last stone that was not thrown out in this game. As the id of the stone that was left is the same as the number of stones he started with, he ends his game. Then he announces 3 as his favorite number.

To be precise, at first he takes **N** stones, and arranges them in a **circle**. Then he throws out every **second** stone in the circle until there is only one stone in the circle. If **x1** is the id of last stone that is not thrown out, he first checks if **x1** is the number of stones the circle had before he began throwing out the stones (in this case, the number is **N**). So he checks if **x1 = N**. If the both the numbers are equal, then he stops his game and decides that **x1** is his favorite number. If the numbers are not equal he arranges **x1** stones in a different new circle, and again, throws every **second** stone out. Then if the last stone that was not thrown out is **x2**, then he again checks if the number **x2** is the number of stones he had in this circle. He had **x1** stones before this round started. So he checks if **x1 = x2**. If the numbers are equal, he stops his game, and decides that **x2** is his favorite number. Otherwise he continues the game with **x2** stones. The game goes on like this until the result of a game starting with **xi** stones ends with a stone with id **xi** left. Then Abir decides that **xi** is his **favorite number**.

Initially, Abir started playing with **N** stones in a circle. After finishing his game, he found that **x** is his favorite number. Seeing this, his best friend Nabil also wants **x** to be his favorite number. He thought of the following question, How many different integers with value L are there, between 1 and 2K - 1(inclusive) such that if I played the game with L stones, I can also decide x as my favorite number just like Abir's? Can you help him? As the number can be very large, print it **modulo (109 + 7)**

The first line will contain **T**. The number of test cases. Each of the next **T** lines will contain 2 integers each. Each line will contain the value of **N** and **K** separated with a space.

**Constraints**

**1 ≤ T ≤ 10****1 ≤ N ≤ 1018****1 ≤ K ≤ 100000**

Subtask 1(10 Points)**1 ≤ T ≤ 5****1 ≤ N ≤ 50****1 ≤ K ≤ 5**

Subtask 2(20 Points)**1 ≤ T ≤ 10****1 ≤ N ≤ 1000000****1 ≤ K ≤ 5**

Subtask 3(30 Points)**1 ≤ T ≤ 5****1 ≤ N ≤ 10000000****1 ≤ K ≤ 20**

Subtask 4(40 Points)

Original Constraints

For each of the test cases, you have to output the number of different integers with value **L** that is between 1 and 2K - 1 inclusive such that if the game was played with **L** stones, the favorite number will be same as the game is played with **N** stones. Print the answer modulo (109 + 7).

Input | Output |
---|---|

2 10 4 11 4 | 6 4 |