[중등 극심화] 두 공이 충돌하지 않을 확률

아래와 같은 장치의 두 입구에 공 두 개를 동시에 넣었을 때, 두 공이 한 번도 충돌하지 않고 두 출구로 나올 확률이 $\dfrac{n}{m}$이다. 서로소인 두 자연수 $n$, $m$에 대해 $n+m$의 값을 구하시오.

(단, 장치의 모든 통로 구간의 길이는 같고 두 공은 같은 일정한 속력으로 움직인다. 각 공이 갈림길에서 오른쪽이나 왼쪽으로 이동할 확률은 같으며, 각 선택은 이전의 선택 및 다른 공의 선택과 서로 독립이다. 두 공이 같은 시각에 같은 지점에 도달하면 충돌한 것으로 본다.)