El Toll Caves

El Toll의 선사 시대 동굴은 Moià (Barcelona)에 있다. 당신은 동굴 안의 가능한 지점 n곳 중 한 곳에 보물이 숨겨져 있다고 들었다. 각 지점에 보물이 있을 확률은 1 / n이라고 가정한다.

당신은 직접 동굴에 들어갈 수 없으므로, 동굴에서 보물을 찾을 수 있는 로봇을 만들었다. 매일 로봇에게 동굴 안의 서로 다른 지점 정확히 k곳을 방문하도록 지시할 수 있다. 이 지점들 중 어느 곳에도 보물이 없다면 로봇은 당연히 빈손으로 돌아온다. 하지만 동굴은 어둡기 때문에 로봇이 올바른 지점을 방문하더라도 보물을 놓칠 수 있다. 형식적으로, 방문한 지점 중 한 곳에 보물이 있다면 로봇은 1 / 2의 확률로 보물을 획득하고, 그렇지 않으면 빈손으로 돌아온다. 로봇이 보물이 있는 지점을 탐색할 때마다 성공 확률은 이전의 모든 시도와 독립적이다. 즉, 올바른 지점을 x번 탐색한 뒤에도 보물을 놓칠 확률은 1 / 2x이다.

로봇의 일정을 최적으로 선택할 때 보물을 획득하는 데 걸리는 날짜 수의 기댓값은 얼마인가? 답을 109 + 7로 나눈 유리수로 출력한다. 형식적으로 답을 기약분수 P / Q라고 할 때, 를 출력해야 한다. Q가 109 + 7로 나누어떨어지지 않음이 보장된다.

첫 번째 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 1000)가 주어진다.

다음 T개의 각 줄에는 두 정수 n와 k (1 ≤ k ≤ n ≤ 5·108)가 주어진다.

각 테스트 케이스의 답을 별도의 줄에 출력한다.

첫 번째 경우에는 로봇이 유일한 지점을 반복해서 탐색한다. 이 경우 날짜 수의 기댓값은 2이다. 처음부터 보물이 있는 지점을 알고 있음에도 로봇이 보물을 성공적으로 회수할 때까지 그곳을 계속 탐색해야 한다는 점에 유의한다.

두 번째 경우에는 두 지점을 번갈아 탐색하면 답이 7 / 2와 같음을 보일 수 있다. 세 번째 경우의 답은 25 / 9이다.