Solution:

Since segments $\overline{AC}$ and $\overline{BD}$ cross, $A$ and $C$ lie on opposite sides of the square, as do $B$ and $D.$ Let $m$ be the slope of the side through $B,$ so that side lies on $mx - y + 9 - 10m = 0,$ and the perpendicular side through $C$ lies on $x + my - 8 = 0.$ The side length of the square equals both the distance between the parallel sides through $B$ and $D$ and the distance between the sides through $A$ and $C:$ $$\frac{|{-4m} - 7 + 9 - 10m|}{\sqrt{m^2 + 1}} = \frac{|12m - 8|}{\sqrt{m^2 + 1}},$$ so $|2 - 14m| = |12m - 8|,$ giving $m = \frac{5}{13}$ or $m = -3.$

For $m = \frac{5}{13},$ the points $A$ and $C$ fall on opposite sides of the line through $B,$ which is impossible if that line contains a side of the square, so $m = -3.$ Then the side length is $\frac{|12(-3) - 8|}{\sqrt{9 + 1}} = \frac{44}{\sqrt{10}},$ so $$K = \frac{44^2}{10} = \frac{1936}{10} \qquad \text{and} \qquad 10K = 1936.$$

The remainder when $1936$ is divided by $1000$ is $936.$