Permutations

You are given a set $S$, which is a subset of $\{1, 2, \ldots, N\}$. Consider a permutation $P_1, P_2, \ldots, P_N$ of the integers $1$ through $N$. The cost of this permutation is the number of indices $i \gt 1$ such that $P_i$ is divisible by $P_{i-1}$ and $\frac{P_i}{P_{i-1}} \in S$. For each $k$ between $0$ and $N-1$ (inclusive), find the number of permutations with cost $k$. Since these