Identities and Techniques, Proved · Hard problem

Let $S=\{1,2,3,4,5,6\}$. Over all $4^6$ ordered pairs $(A,B)$ of subsets of $S$ (each may be empty, and they may be equal), find the sum of $|A\cap B|$.