28695번 - 양말 부자 동우와 츤데레 재우

문제

동우는 빨래할 때 양말은 양말끼리 빨래 바구니에 모아 두었다가 빨래를 돌리는 습관이 있다. 그런데 빨래하던 동우는 항상 빨래가 끝나면 양말이 짝이 맞지 않고 한 짝이 사라진다는 미스터리를 알게 되었다. 이에 동우는 양말 빨래를 할 때 양말의 짝을 맞추기 위해, 빨래 바구니에 들어 있는 양말을 다음과 같은 규칙의 시행을 통해 세탁기에 넣기로 했다.

• 빨래 바구니에 남아 있는 양말 중 한 짝을 무작위로 꺼낸다.
• 이미 바닥에 놓여진 양말 중 방금 꺼낸 양말과 같은 종류의 양말이 있다면 해당 양말과 함께 양말 두 짝(한 쌍)을 세탁기에 넣는다.
• 만약 방금 꺼낸 양말과 같은 종류의 양말이 바닥에 놓여져 있지 않다면, 방금 꺼낸 양말을 바닥에 놓는다.

동우는 양말 부자이기 때문에, 총 $n$종류의 양말을 가지고 있으며, 종류별로 무수히 많은 양말이 빨래 바구니에 들어있다. 동우는 위의 규칙으로 세탁기에 양말을 넣다가 너무 힘들어 잠시 쉬기로 했다. 힘들어하는 동우를 본 츤데레 재우는 동우가 잠시 쉬는 동안 동우를 대신해 위의 규칙에 맞게 시행해 동우를 돕기로 했다.

재우는 츤데레이기 때문에, 동우가 눈치를 채지 않게 하고 싶다. 동우는 상당히 둔하므로 양말의 개수만 같다면 상태가 변하지 않았다고 생각한다. 따라서 재우는 $m$번의 시행 후에 양말의 개수가 변하지 않게 하고 싶다. 즉, 재우가 $t$번 시행한 후 바닥에 놓여져 있는 양말의 개수를 $f(t)$라고 정의할 때, $m$번 시행 후 $f(m)$이 $f(0)$와 같아지도록 하고 싶다.

동우가 쉬기 시작할 때, 즉 재우가 시행하기 전에 놓여져 있는 양말의 개수 $f(0)$가 0ドル$부터 $n$까지 가능한데, 각각의 경우에 대해 $\frac{1}{n+1}$의 동일한 확률을 가진다. 이때, $m$번 시행 후 $f(m)=f(0)$일 확률을 구해보자.

각 시행마다 양말을 빨래 바구니에서 꺼낼 때 각 종류의 양말에 대해 $\frac{1}{n}$의 동일한 확률로 꺼낸다.

입력

첫 줄에 테스트케이스의 개수 $T(1\le T\le 100)$이 주어진다.

각 테스트케이스 별로 한 줄에 하나씩 양말의 종류의 개수를 의미하는 정수 $n(1\le n \le 10^{9})$과 재우가 할 시행의 횟수 $m(0\le m \le 10^{9})$이 공백으로 구분되어 주어진다.

모든 테스트케이스의 $\min(n,m)$의 합은 10ドル^6$ 이하임이 보장된다.

출력

첫 줄에 $f(m)=f(0)$일 확률을 10ドル^9+7$로 나눈 나머지를 공백으로 구분하여 출력하라. 단, 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$를 의미한다.

$n$을 10ドル^9+7$로 나눈 나머지가 0ドル$ 혹은 10ドル^9+6$이 아닌 입력만 주어진다. 이 경우 나머지가 유일하게 결정되며, 답은 정수이거나 기약분수로 나타냈을 때 분모가 10ドル^9+7$과 서로소인 경우만 주어진다.

제한

힌트

양말 한 짝은 한 개를 의미하며 두 짝이 한 쌍이다. 또한, 양말의 왼쪽과 오른쪽의 구분이 없어 같은 종류면 쌍을 이룬다.