Пусть $t_n$ будет последовательностью чисел трибоначчи, определенной как:
$t_0 = t_1 = 0$;
$t_2 = 1$;
$t_n = t_{n-1} + t_{n-2} + t_{n-3}$ для $n \ge 3$
и пусть $r_n = t_n \text{ mod } 10^7$.

Для каждой пары векторов $V_n=(v_1,v_2,v_3)$ и $W_n=(w_1,w_2,w_3)$ с $v_1=r_{12n-11}-r_{12n-10}, v_2=r_{12n-9}+r_{12n-8}, v_3=r_{12n-7} \cdot r_{12n-6}$ и
$w_1=r_{12n-5}-r_{12n-4}, w_2=r_{12n-3}+r_{12n-2}, w_3=r_{12n-1} \cdot r_{12n}$
мы определим $S(n)$ как минимальное значение манхэттенского расстояния вектора $D=k \cdot V_n+l \cdot W_n$, измеряемое как $|k \cdot v_1+l \cdot w_1|+|k \cdot v_2+l \cdot w_2|+|k \cdot v_3+l \cdot w_3|$ для любых целых $k$ и $l$ с $(k,l)\neq (0,0)$.

Первая пара векторов - (-1, 3, 28), (-11, 125, 40826).
Известно, что $S(1)=32$ и $\sum_{n=1}^{10} S(n)=130762273722$.

Найдите $\sum_{n=1}^{20000000} S(n)$.