We prove that any AC0 circuit augmented with {epsilon log^2 n}
MOD_m gates and with a MAJORITY gate at the output, require size
n^{Omega(log n)} to compute MOD_l, when l has a prime
factor not dividing m and epsilon is sufficiently small. We
also obtain that the MOD_2 function is hard on the average for
AC0 circuits of size n^{epsilon log n} augmented with
{epsilon log^2 n} MOD_m gates, for every odd integer m and
any sufficiently small epsilon. As a consequence, for every
odd integer m, we obtain a pseudorandom generator, based on the
MOD_2 function, for circuits of size S containing epsilon
log S MOD_m gates.

Our results are based on recent bounds of exponential sums that were
previously introduced for proving lower bounds for
MAJ o MOD_m o AND_d circuits.