数列の中には1つだけ同じ数値が2回出現する. この位置を \(i, j\) とする.

部分文字列で重複するのは, \([1, i-1]\) の区間から \(x\) 文字, \(i, j\) のどちらか1文字, \([j+1, n]\) の区間から \(y\) 文字を選んだときであるので, 長さ \(k\) の部分文字列の組み合わせの数は,

\[{}_{n+1}C_k - {}_{i-1+n-(j+1)}C_{k-1}\]

となる. 階乗と逆元はあらかじめ計算しておく.