2010 AIME I Problem 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}.