Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an n -variate boolean function has circuit complexity less than a given parameter s . We prove that MCSP is hard for constant-depth circuits with mod p gates, for any prime p 2 (the circuit class A C 0 [ p ]) . Namely, we show that MCSP requires d -depth A C 0 [ p ] circuits of size at least exp ( N 0 49 d ) , where N = 2 n is the size of an input truth table of an n -variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random N -bit strings from those generated using independent samples from a biased random coin which is 1 with probability 1 2 + N − 0 49 , and 0 otherwise. Solving the coin problem with such parameters is known to require exponentially large A C 0 [ p ] circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform A C 0 circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in N C 1 (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size A C 0 circuit with MCSP-oracle gates.