## Editorial for BSSPC '22 P5 - Derrick and Orz Trees

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

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:

Implementing this as above yields . Proof is left as an exercise to the reader. Don't forget to mod.

We can do:

Informal Proof

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

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

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

Applying this logic recursively yields our proof.