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

동우는 빨래할 때 양말을 종류별로 빨래 바구니에 모아 두었다가 빨래를 돌리는 습관이 있다. 그런데 동우는 빨래가 끝날 때마다 양말이 짝을 이루지 못하고 한 짝이 사라진다는 사실을 알게 되었다. 그래서 양말의 짝을 맞추기 위해, 빨래 바구니의 양말을 다음 규칙에 따른 시행을 거쳐 세탁기에 넣기로 했다.

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

동우는 양말 부자여서 총 $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$로 나눈 나머지를 공백으로 구분하여 한 줄에 출력하라.

기약분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는, $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수 $q^{-1}$을 써서 $p\cdot q^{-1}\pmod M$로 정의한다. 정수이면 $q=q^{-1}=1$이므로 $p\pmod M$이다.

기댓값과 분산이 모두 $10^9+7$로 나눈 나머지로 유일하게 정해지는 입력만 주어진다. 즉, 답은 정수이거나 분모가 $10^9+7$과 서로소인 기약분수이다. $10^9+7$은 소수이다.

양말 한 짝은 한 개를 뜻하고, 두 짝이 한 쌍이다. 양말에는 왼쪽과 오른쪽의 구분이 없으므로, 같은 종류끼리는 쌍을 이룬다.