# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 **x _{1}** is the id of last stone that is not thrown out, he first checks if

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 2^{K} - 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 (10 ^{9} + 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 ≤ 10 ^{18}**

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 2^{K} - 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 (10^{9} + 7).

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

2 10 4 11 4 | 6 4 |

11% Solution Ratio

ragibshahriarEarliest,

ragibshahriarFastest, 0.3s

ragibshahriarLightest, 1.4 MB

ragibshahriarShortest, 300B

Login to submit

The basic problem here comes from the Josephus Problem. In Josephus problem, N people stands in a ci... Read more...