32232번 - 엉엉이의 저주 탈출 서브태스크

문제

엉엉이의 저주, 멈뭄미믜 저주, 섯섯시싀 저주에 차례로 걸렸었던 현철이는 섯섯시싀 저주, 멈뭄미믜 저주를 무사히 풀어내고 이제 마지막 관문인 엉엉이의 저주만 남겨두고 있다.

엉엉이는 현철이와 한 원 위에서 하는 게임인 엉엉이 게임을 제안했다. 엉엉이는 자신이 게임을 제안한 만큼, 게임의 공정성을 위해 자신에게 패널티를 부여하기로 했다. 이로 인해 현철이는 최적의 전략으로 플레이할 수 있지만 엉엉이는 모든 행동을 랜덤하게 진행한다. 구체적으로 엉엉이 게임은 다음과 같이 진행된다.

• 엉엉이 게임은 총 $N$턴 동안 진행된다. 첫 번째 턴을 시작하기 전, 게임의 턴 수 $N$과 게임 상수 $M$을 정한다. 이때, $N$은 1ドル$이상의 정수, $M$은 3ドル$이상의 정수이다.
• 첫 번째 턴부터 $N$번째 턴까지 $i$번째 턴에 다음 행동을 진행한다.
  • 현철이는 3ドル$이상 $M$이하의 정수 $t_i$를 동일한 확률로 하나 뽑는다.
  • 이어 현철이는 원주 위에 서로 다른 $t_i$개의 점을 원하는 대로 고르고, 고른 점들을 이어 볼록 $t_i$각형을 그린다.
  • 엉엉이는 3ドル$이상 $M$이하의 정수 $s_i$를 동일한 확률로 하나 뽑는다.
  • 이어 엉엉이는 원주 위에 균일한 확률로 서로 다른 $s_i$개의 점을 뽑고, 뽑은 점들을 이어 볼록 $s_i$각형을 그린다.
• 현철이와 엉엉이는 모든 턴이 종료될 때 까지 서로의 그림을 볼 수 없다. 또한, 모든 턴이 종료될 때까지 서로의 $t_i$와 $s_i$를 알 수 없다.
• 모든 턴이 종료된 후 서로의 그림을 겹친 후, 원이 몇 개의 조각으로 나뉘었는지 확인한다. 이때, 짝수 개의 조각으로 나뉘었다면 현철이가 이기며, 홀수 개의 조각으로 나뉘었다면 엉엉이가 이긴다.

$N=2,ドル $M=5$일 때의 예시이며, 원은 44개의 조각으로 나뉘었다.

위의 그림이 현철이의 최적의 전략이 아닐 수 있다.

게임의 턴 수 $N$과 게임 상수 $M$이 정해졌을 때, 현철이가 최적의 전략으로 게임을 했을 때 이길 확률을 출력해 보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^6)$가 주어진다.

다음 $T$개의 줄에 걸쳐 게임의 턴 수와 게임 상수를 나타내는 양의 정수 $N(1\le N\le 10^9)$과 $M(3\le M\le 10^9)$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄부터 $T$개의 줄에 걸쳐 각 테스트 케이스 별로 현철이가 이길 확률을 출력해보자. 단, 정확한 출력을 위해 현철이가 이길 확률을 10ドル^9+7$로 나눈 나머지를 출력한다.

기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

주어진 조건 내에서 정답이 정수 혹은 분모가 10ドル^9+7$의 배수가 아닌 유리수로 나타내어짐을 증명할 수 있다.

제한

서브태스크

힌트