Floresta

O desmatamento é um dos maiores problemas enfrentados pelo Brasil hoje; estima-se que mais de 10 mil km² de vegetação sejam desflorestados todo ano. Além de destruir os habitats de várias espécies em risco de extinção, o desmatamento promove a emissão de gás carbônico, principal responsável pelo efeito estufa e pelo aquecimento global.

A Fundação de Conservação dos Carvalhos (FCC) tenta combater esta tendência, promovendo o reflorestamento das regiões desmatadas. Para isso, eles pretendem plantar carvalhos formando um quadriculado (um carvalho em cada vértice); no centro de cada quadrado formado por eles, a FCC também plantará um eucalipto. Para preservar a biodiversidade da área plantada, pelo menos uma árvore de cada espécie deve ser plantada durante o reflorestamento.

Por exemplo, se a FCC quiser plantar 23 árvores, ela poderá fazê-lo de duas maneiras: ou formando um retângulo 3 × 5 com os carvalhos, como na figura (a), ou formando um retângulo 2 × 8, como na figura (b). Considere que, para os propósitos deste problema, um retângulo X×Y é equivalente a um retângulo Y×X.

Sua tarefa é escrever um programa que, dado o número total de árvores que devem ser plantadas, de quantas maneiras diferentes elas podem ser dispostas.