Rename each of $1, 2, 3, 4$ as L and each of $6, 7, 8, 9$ as G. If $5$ is not a row median, then no row median equals $5,$ so $m \neq 5.$ Thus $5$'s row must contain one L and one G (reading L5G in some order), and the other two rows must supply one median below $5$ and one above. With the remaining three L's and three G's, those rows are either LLL and GGG, or LLG and LGG.

Count arrangements of letters: the three row types can be assigned to rows $1, 2, 3$ in $3! = 6$ ways, and the L5G row can be ordered in $3! = 6$ ways. In the first case LLL and GGG have $1$ ordering each, giving $6 \cdot 6 \cdot 1 = 36$ patterns; in the second, LLG and LGG each have $3$ orderings, giving $6 \cdot 6 \cdot 9 = 324$ patterns. That is $360$ letter patterns in all.

Finally the four L's can be filled with $1, 2, 3, 4$ in $4!$ ways and the four G's with $6, 7, 8, 9$ in $4!$ ways, so $Q = 360 \cdot 24^2 = 207360,$ whose remainder mod $1000$ is $360.$