**Corollary 6**
There exist 0<

*c*<1 and 0<

*c*'<1, such that if the

*n* fan-in AND function is computed by a circuit with a MOD

^{B}_{q} gate at the top, MOD

^{A}_{p} gates at the next level, where the inputs of each MOD

^{A}_{p} gate is

*an arbitrary integer-valued function* of

*cn* variables plus an arbitrary linear polynomial of

*n* variables, then the circuit must contain at least 2

^{c'n} MOD

^{A}_{p} gates.