The Garner Builder: Incremental CRT Reconstruction

In the engineering halls of Prime City, the Royal Architect uses the Garner algorithm to reconstruct a number from its CRT residues incrementally. Unlike the standard CRT which computes the solution all at once, the Garner algorithm builds the solution digit by digit in a mixed-radix representation, which is more efficient for repeated computations with the same moduli. "The Garner algorithm expresses x = v0 + v1*m1 + v2*m1*m2 + ... where vi are computed from the residues and modular inverses," the Architect explains. "This mixed-radix form allows efficient computation and is used in high-performance RSA implementations." Given k pairwise coprime moduli m1..mk and residues r1..rk, find x in the range [0, product(m1..mk)-1] using the Garner algorithm. Output x. Constraints: 1 <= k <= 10, 1 <= ri < mi <= 10^9, pairwise coprime, product <= 10^18 Input: 3 2 3 5 1 2 3 Output: 11 Input: 2 3 5 2 4 Output: 14