경희대학교 알고리즘 동아리 KHUA에서는 축하할 일이나 기념할 일이 있을 떄 선물로 수열을 주고받는 PS계의 문화를 본받아 신입 부원들에게 선물로 수열을 나누어 주려고 한다. 하지만 매번 새로운 수열을 만들어 내는 것은 귀찮기 때문에 수열 하나를 만들어 두고 그것을 재활용해서 새로운 수열을 만들어 내기로 했다.

재활용할 무한한 길이의 주기 수열 A₁, A₂, ...를 만든다. A의 첫 N개 원소는 A₁, A₂, ..., A_N로 주어지며, i > N일 때 A_i = A_i - N이다. 이 수열의 각 원소는 0 이상 M - 1 이하의 정수이다. 1 이상 N 이하인 정수 i와 0 이상 M - 1 이하의 정수 j에 대해 다음과 같이 정의되는 길이 T (T ≤ N)인 수열 B^i, j₁, B^i, j₂, ..., B^i, j_T을 선물로 나누어 주면 좋겠다고 생각했다.

하지만 이렇게 만들어진 수열이 중복되면 사람들이 수열을 재활용하고 있다는 걸 알아챌 수 있으므로 이런 상황은 최대한 피하려고 한다.

재활용해 만들어낸 임의의 두 수열이 같을 확률을 구해 얼마나 수열을 재활용할 수 있을 지 예측하려고 한다. 1 ≤ i₁, i₂ ≤ N이고 0 ≤ j₁, j₂ ≤ M - 1인 정수 i₁, i₂, j₁, j₂를 균일한 확률로 무작위로 뽑았을 때 B^i₁, j₁과 B^i₂, j₂가 서로 같을 확률을 구해야 한다. 각 수는 독립적으로 선택되므로 (i₁, j₁) = (i₂, j₂)인 경우도 발생할 수 있다. 이 경우를 포함하여 확률을 구해야 한다.