Answer: 360

Small Hint:

Rename each number less than $5$ as L and each greater as G. For $m = 5,$ the number $5$ must be a row median, so its row reads L5G in some order.

Big Hint:

The other two rows need medians on opposite sides of $5:$ LLL with GGG, or LLG with LGG. Count letter patterns, then multiply by $(4!)^2$ for actual values.

Solution:

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,$ and $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.$