35291번 - 선물 게임

mythofys는 외국에서 유행하는 선물 상자를 밟아서 목적지까지 도착하되, 빈 상자를 밟으면 안되는 게임을 흥미롭게 보았다. 그래서 수아와 피씨에게 이 게임을 시켜보기로 하였다.

구체적으로 게임은 다음과 같이 진행된다. 수아가 먼저 시작하여 피씨와 번갈아 가며 차례를 갖는다. 이때, 선물 상자는 한 열에 $N$개가 있고, 그 중 정확히 한 개의 선물 상자만 진짜 선물 상자이고, 나머지 선물 상자는 모두 가짜 선물 상자이다. 두 플레이어는 차례가 돌아올 때마다 첫 열의 선물 상자부터 밟게 된다. 각 열의 진짜 선물 상자를 밟았을 경우 다음 열의 선물 상자를 밟을 수 있는 기회가 주어진다. 가짜 선물 상자를 밟은 경우, 차례를 바꾼다.

게임은 이런 열이 총 $M$개 존재하여 $N \times M$개의 선물 상자들로 구성되고, 마지막 열의 진짜 선물 상자를 밟은 사람이 승리한다. 이때, 선물 상자를 밟는 과정은 서로에게 공개되기 때문에 서로가 진짜 선물 상자를 밟았는지 가짜 선물 상자를 밟았는지는 알 수 있다. 서로 이기기 위해 최선을 다해서 게임을 진행할 때, 수아가 이길 확률을 구해야 한다.

이때, 확률은 기약분수로 출력하되, 분자와 분모의 값이 너무 클 수 있으므로 기약분수 $\frac{a}{b}$로 나타냈을 때, $a$를 $10^9$으로 나눈 나머지, $b$를 $10^9$으로 나눈 나머지를 출력하여라.

첫 번째 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 10^6$)

수아가 이길 확률을 기약분수로 나타낸 후 분자를 $a$, 분모를 $b$라고 할 때, $a$를 $10^9$으로 나눈 나머지, $b$를 $10^9$으로 나눈 나머지를 공백으로 구분하여 첫 번째 줄에 출력한다.