A permutation of $\{2,3,\dots ,n\}$ is a rearrangement of these numbers. A coprime permutation is a rearrangement such that all pairs of adjacent numbers are coprime.

Let $P(n)$ be the number of coprime permutations of $\{2,3,\dots ,n\}$.

For example, $P(4)=2$ as there are two coprime permutations, $(2,3,4)$ and $(4,3,2)$. You are also given $P(10)=576$.

Find $P(34)$ and give your answer modulo $83456729$.