2010 AIME I Question 7

Define an ordered triple $(\mathcal{A}, \mathcal{B}, \mathcal{C})$ of sets to be *minimally intersecting* if $|\mathcal{A} \cap \mathcal{B}| = |\mathcal{B} \cap \mathcal{C}| = |\mathcal{C} \cap \mathcal{A}| = 1$ and $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset.$ For example, $(\{1, 2\}, \{2, 3\}, \{1, 3, 4\})$ is a minimally intersecting triple. Let $N$ be the number of minimally intersecting ordered triples of sets for which each set is a subset of $\{1, 2, 3, 4, 5, 6, 7\}.$ Find the remainder when $N$ is divided by $1000.$

Note: $|\mathcal{S}|$ represents the number of elements in the set $\mathcal{S}.$