Máquinas sem nomes

Uma máquina tem $n$ estados. Cada estado possui exatamente uma transição de saída, cujo destino pode ser qualquer estado, inclusive ele mesmo. Não existe estado inicial, estado final, rótulo nas transições ou outra informação associada aos estados.

Se numerássemos os estados de $1$ a $n$, uma máquina seria descrita por uma função $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$: a transição de saída de $u$ leva a $f(u)$. A função não precisa ser injetiva ou sobrejetiva. A máquina pode ter várias componentes desconectadas.

Os nomes dos estados não importam. Duas funções $f$ e $h$ descrevem a mesma máquina se existe uma permutação $\pi$ dos estados tal que

$h(\pi(u))=\pi(f(u))$

para todo estado $u$. Ou seja, uma mesma renomeação deve ser aplicada às origens e aos destinos das transições.

Conte as máquinas diferentes com exatamente $n$ estados, módulo $1\,000\,000\,007$.

2

3

3

7

1

1