Рассмотрим горизонтальную свободную от трения трубу длиной $L$ миллиметров и диаметром 20 миллиметров. Восточный конец трубы открыт, а западный - закрыт. В трубе в определенных начальных положениях находятся $N$ шариков диаметром 20 миллиметров, каждый из них изначально движется на запад или на восток с одинаковой скоростью $v$.

Так как есть шарики, движущиеся в противоположные стороны, между ними неизбежны столкновения. Мы полагаем, что столкновения идеально эластичны и оба столкнувшихся шарика мгновенно меняют направление движения и продолжают двигаться от места столкновения со скоростью $v$. Таким же образом, если самый западный шарик столкнется с закрытым концом трубы, он мгновенно изменит направление движения и продолжит двигаться на восток со скоростью $v$. С другой стороны, если шарик достигнет открытого восточного конца, он покинет трубу и больше не взаимодействует с оставшимися шариками.

Чтобы получить начальные положения и направления движения шариков, используем псевдослучайную последовательность $r_j$, заданную следующим образом:
$r_1 = 6\,563\,116$
$r_{j+1} = r_j^2 \bmod 32\,745\,673$
Самый западный шарик изначально размещается на расстоянии $(r_1 \bmod 1000) + 1$ миллиметров от закрытого конца трубы, считая от самой западной точки на поверхности шарика. Затем, для $2\le j\le N$, считая с запада на восток, расстояние между $(j-1)$-тым и $j$-тым шариком, отмеренное между их ближайшими точками, задано как $(r_j \bmod 1000) + 1$ миллиметров. Наконец, $j$-тый шарик изначально движется на восток, если if $r_j \le 10\,000\,000$, или на запад, если $r_j > 10\,000\,000$.

Например, при $N=3$, последовательность определяет расстояния в 117, 432 и 173 миллиметра. Таким образом, центры шариков находятся на расстоянии 127, 579 и 772 миллиметров от закрытого конца трубы. Самый западный шарик изначально движется на восток, а остальны два - изначально на запад.

При таком исходном состоянии и длине трубы 5 метров ($L=5000$), оказывается, что средний (второй) шарик пройдет путь 5519 миллиметров до того, как его центр достигнет восточного конца трубы.

Пусть $d(L, N, j)$ будет длиной пути $j$-того шарика, пройденного им до того, как его центр достигнет восточного конца трубы. Таким образом, $d(5000, 3, 2) = 5519$. Также известно, что $d(10\,000, 11, 6) = 11\,780$ и $d(100\,000, 101, 51) = 114\,101$.

Найдите $d(1\,000\,000\,000, 1\,000\,001, 500\,001)$.