He does not need to visit the same zoo three or more times, so the answer can be found by brute-forcing all the choices of the number of times to visit each zoo from \(0\), \(1\), or \(2\) times.

Once the number of times to visit the zoos have been fixed, the number of times he sees each animals can be naively counted in \(O(NM)\) time, so the total computational complexity is \(O(3^NNM)\).

Implementation exercise: ABC263C