The parameter of $p-MC(Φ)$ is computable in polynomial time. An IMP+ program reads the word, skips the structure using its header (the number of symbols, the arities, the size, then per symbol the number of tuples, each block being that number times the arity long), and walks the prefix code of the formula to the end of the word, adding up the contribution of each tag; it runs in $O(|x|)$ steps.