先不考虑钦定一个数的限制。打表发现是斐波那契。但我们要会证明。

观察 $1$ 的位置。设为 $i+1$。则有 $i\cdot p_i\le i+1$，即 $p_i\le \frac{i+1}i$。由于 $p_i\neq 1$ 且有解，所以 $\frac{i+1}i\ge 2$，得到 $i\le 1$。所以 $1$ 只能放前两个。

类似地，可以证明 $i$ 只能放在 $i-1$ 或 $i$ 或 $i+1$，且前 $i$ 个数只能放在前 $i+1$ 个位置，且空位必须在后两个。设 $f_i$ 表示前 $i$ 个放前 $i$ 个位置的方案数，$g_i$ 表示前 $i$ 个放前 $i+1$ 个位置，把 $i$ 空出来的方案数，所求即 $f_n$。有转移：$f_{i+1}=f_i+g_i,g_{i+1}=f_i$。替换得 $f_{i+1}=f_i+f_{i-1}$。

这样不好直接做钦定一个数，毕竟不好优化。可以发现合法排列可以由 $1,2,\dots,n$ 交换邻项得到，且每一个数最多交换一次。写一个一样的 dp 发现也是斐波那契。但是这样更好做钦定 $a_x$。若 $a_x=x$，即此项不动，方案数即为前后缀斐波那契乘积。若 $a_x=x-1$，即交换了这项和前一项，方案数仍为前后缀斐波那契乘积。剩下一种也一样。

所以预处理个斐波那契做完了。朴素做 $T+n$，矩阵可以做 $T\log n$。