## Editorial for Mock CCC '19 Contest 1 S4 - Pusheen Plays Neko Atsume

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.

This problem is a homage to CCC 2018 S4, which tripped up competitors who needed to constant optimize dynamic programming algorithms.

For the first subtask, the answer was guaranteed to be a power of two, as the recurrence collapses into being the product of two and an earlier term in the recurrence. This means that the query can be answered in by seeing how many steps it takes to get to a term of in the recurrence.

As a final implementation detail, an array of ints is much faster than a map or dict.