28694번 - 양말 부자 동우와 착한 하늘이

문제

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

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

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

문득 하늘이는 몇 번의 시행 이후 바닥에 놓여져 있는 양말의 개수에 대해 궁금해졌다. 하늘이가 $m$번 시행한 후 바닥에 놓여져 있는 양말 개수의 기댓값과 분산을 구해보자.

동우는 충분히 많이 시행했기 때문에, 동우가 쉬기 시작할 때, 즉 하늘이가 시행하기 전에 각 종류의 양말이 바닥에 놓여 있을 확률은 각각의 양말의 종류에 대해 독립적으로 $\frac{1}{2}$이다. 즉, 2ドル^n$가지의 가능한 초기 상태에 대해 모두 확률이 $\frac{1}{2^n}$로 동일하다.

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

입력

첫 줄에 테스트 케이스의 개수를 의미하는 정수 $T(1\le T\le 10^{5})$이 주어진다.

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

출력

각 테스트 케이스 별로 한 줄에 하늘이가 $m$번 시행한 후 바닥에 놓여져 있는 양말의 개수의 기댓값과 분산을 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$를 의미한다.

모든 테스트 케이스에 대해 기댓값과 분산을 10ドル^9+7$로 나눈 나머지가 유일하게 결정되는 입력만 주어진다. 즉, 답은 정수이거나 기약분수로 나타냈을 때 분모가 10ドル^9+7$과 서로소인 경우만 주어진다.

제한

힌트

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