엉엉이의 저주 탈출

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

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

• 엉엉이 게임은 총 $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\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수 $q^{-1}$, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원을 써서 $p\cdot q^{-1}\pmod M$로 정의한다. 값이 정수이면 $q=q^{-1}=1$이므로 $p\pmod M$을 뜻한다.

주어진 조건에서 정답이 정수이거나, 분모가 $10^9+7$의 배수가 아닌 유리수로 나타낼 수 있음을 증명할 수 있다.