An $n \times n$ matrix is called squareful if it satisfies the following conditions:

• each number from $1$ to $n^2$ appears exactly once;
• each pair of consecutive numbers are orthogonally adjacent;
• for each $k \lt n$, the numbers $1$ to $k^2$ form a contiguous square submatrix.

For example, the matrix $$\begin{pmatrix} 13 & 14 & 15 & 16\\ 12 & 1 & 4 & 5\\ 11 & 2 & 3 & 6\\ 10 & 9 & 8 & 7 \end{pmatrix}$$ is a $4 \times 4$ squareful matrix. Its traceThe trace of a matrix is the sum of the elements on its main diagonal, from the top-left corner to the bottom-right corner. is $13 + 1 + 3 + 7 = 24$.

Let $T(n)$ be the sum of the traces of all squareful matrices whose size does not exceed $n \times n$.
For example, $T(2) = 41$, $T(12) = 9063089$ and $T(123) \equiv 1139320302 \bmod 1234567891$.

Find $T(123456789) \bmod 1234567891$.