매우 간단한 문제

깊이가 $H$인 완전 $K$-진 트리에서 임의의 서로 다른 두 정점 사이의 거리의 기댓값을 계산하라.

완전 $K$-진 트리란, 리프 정점(자식이 없는 정점)을 제외한 모든 정점이 $K$개의 자식 정점을 지닌 트리를 의미한다.

완전 $K$-진 트리에서 모든 리프 정점은 항상 루트 정점으로부터 $H - 1$만큼 떨어져 있다.

각각의 정점은 균등한 확률으로 선택된다.

첫 번째 줄에 정수 $Q$가 주어진다.

두 번째 줄부터 $Q$개의 줄 중 $i$번째 줄에 두 정수 $H\_i$와 $K\_i$가 공백으로 구분되어 주어진다.

$Q$개의 줄에 걸쳐, $i$번째 줄에 깊이가 $H\_i$인 $K\_i$-진 트리에서 임의의 두 정점 사이의 거리의 기댓값을 출력하여라. 단, 서로 다른 두 정점을 고를 수 없는 경우에는 $0$을 출력하여라.

기댓값은 항상 유리수임을 보일 수 있다. 이 유리수를 기약분수 형태로 나타내면 $\frac{a}{b}$라 할 때, $(a \cdot b^{-1}) \bmod 1\\,000\\,000\\,007$을 출력하여라. 이때 $1\\,000\\,000\\,007$은 소수이다.

어떤 소수 $p$와 정수 $a,b$에 대해 $\gcd(b,p)=1$이라면, $(a \cdot b^{-1}) \bmod p$는 $bx \equiv a\pmod{p}$를 만족하는 가장 작은 음이 아닌 정수 $x$로 정의된다.

$b$가 $1\\,000\\,000\\,007$의 배수인 테스트 케이스는 입력으로 주어지지 않는다.

• $1 \leq Q \leq 1\\,000\\,000$
• $1 \leq H\_i \leq 10^9$ ($1 \leq i \leq Q$)
• $1 \leq K\_i \leq 10^9$ ($1 \leq i \leq Q$)