Note that the trees are independent, and can be considered individually.

As such, the question is: how many gardens can a single tree produce?

For each tree, if it's odd we can't do anything. If it's even, we can either not cut it, or cut it into two halves, each of which we should consider separately. Mathematically:

$$\displaystyle f(h) = f\left(\frac{h}{2}\right) * f\left(\frac{h}{2}\right) + 1$$

Implementing this as above yields ~\mathcal O(\sum_{i = 1}^N H_i)~. Proof is left as an exercise to the reader. Don't forget to mod.

We can do:

$$\displaystyle f(h) = f\left(\frac{h}{2}\right)^2 + 1$$

instead. This gives us ~\mathcal O(N \log H_i)~.

Suppose we have a garden ~G~ produced from ~H~. We can show that this garden can only be produced in one way.

In particular, consider the prefix of ~G~ that sums to ~H_1~. There must be such a prefix, and furthermore, there is exactly one such prefix.

This prefix must have been created by cutting down ~H_1~, and can not have been created in any other way.

Applying this logic recursively yields our proof.