设 $cnt_k$ 表示 $1\sim n$ 中约数个数为 $k$ 的数的个数。
每一组内部可以任意排列，方案数是 $cnt_k!$。
所以总答案：

求 $cnt_k$ 可以使用埃筛，最大筛到 $8 \times 10^6$ 即可。

模数 $500009$ 是质数。如果某个 $cnt_k\ge 500009$，阶乘里就含因子 $500009$，整个乘积变成 $0$，后面的答案也全是 $0$。

注明：此为AI思路（仅思路），请谨慎看待，别点踩，球球了。