Nombre de particions P14519

El curs acadèmic 2024-2025 de la FME s’ha dedicat al matemàtic hindú Srinivasa Ramanujan qui, entre d’altres problemes, va estudiar la funció $p(n)$ que retorna el nombre de particions d’un nombre natural $n$ donat. És a dir, $p(n)$ és el nombre de maneres d’escriure $n$ com a suma de naturals (estrictament positius), sense tenir en compte l’ordre dels sumands.

Per exemple, $p(4) = 5$, perquè el 4 es pot escriure de cinc maneres diferents: $$4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 \enspace .$$ Fixeu-vos que considerem $1 + 3$ i $3 + 1$ com la mateixa suma, i igualment amb $1 + 1 + 2$, $1 + 2 + 1$ i $2 + 1 + 1$.

Com un altre exemple, $p(5) = 7$, perquè el 5 es pot escriure de set maneres diferents: $$5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 \enspace .$$

Podeu calcular $p(n)$?

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i 1000. Els jocs de proves privats tenen molts nombres, possiblement repetits.

Sortida

Per a cada $n$, escriviu $p(n)$ mòdul $10^8 + 7$.