def solve(ns):
    # sum{d} phi(d) * prod{i} n_i//d
    #  group by equal n_i//d
    global PHI
    if not PHI: init_phi()
    naive = sum( PHI[d] * reduce(mul, (n//d for n in ns))
            for d in range(1, min(ns)+1))
    return naive % MOD