
$O(nM(n))$
