Permutation Order II

See Problem 467 - Permutation Order I for definitions.

Let $\mathfrak{A}(n,p)$ be the number of permutations of [1..n] with order p

We have:
$\mathfrak{A}(7,1)=1$
$\mathfrak{A}(7,2)=231$
$\mathfrak{A}(7,3)=350$
$\mathfrak{A}(7,4)=840$
$\mathfrak{A}(7,5)=504$
$\mathfrak{A}(7,6)=1470$
$\mathfrak{A}(7,7)=720$
$\mathfrak{A}(7,10)=504$
$\mathfrak{A}(7,12)=420$

Find the last 10 significant (before trailing 0s) digits of $\mathfrak{A}(1000,641)$

[My timing: < 100 ms]