Перестановка $\{2,3,\ldots,n\}$ - это перестановка этих чисел местами. Взаимно простая перестановка - это такая перестановка местами, при которой все пары соседних чисел являются взаимно простыми.

Пусть $P(n)$ будет количеством взаимно простых перестановок $\{2,3,\ldots,n\}$.

Например, $P(4)=2$, так как существует две взаимно простые перестановки - $(2,3,4)$ и $(4,3,2)$. Также известно, что $P(10)=576$.

Найдите $P(34)$. В качестве ответа приведите остаток от деления полученного числа на $83\,456\,729$.