Q9 Matemática  (KoMaL A Problems 2021)

Um poliomino $P$ ocupa $n$ células de uma grade infinita de quadrados unitários. Em cada movimento, tiramos $P$ da grade e então o colocamos de volta em uma nova posição, possivelmente girada e refletida, de modo que a posição anterior e a nova tenham $n-1$ células em comum. Dizemos que $P$ é uma lagarta de área $n$ se, por meio de uma série de movimentos, pudermos liberar todas as células inicialmente ocupadas por $P$. Quantas lagartas de área $n=10^6+1$ existem? Proposto por Nikolai Beluhov, Bulgária