Let \(A_i\) be the integer when the \(i\)-th row of the adjacency matrix \(A\) is interpreted as a binary notation.

Here, instead of counting the number of tuples of integers \((i,j,k)\) such that \(1 \le i < j < k \le N\), we will consider counting the number of tuples of pairwise distinct integers \((i,j,k)\) where \(1 \le i,j,k \le N\).

When \(i\) and \(j\) is fixed, the number of \(k\) satisfying the conditions is equal to the number of \(k\) such that \(A_{i,k}=A_{j,k}=1\), which is in turn equal to the number of \(1\)’s (set bits) in \(A_i\ \mathrm{AND}\ A_j\).

Thus, we can manage \(A_1,A_2,\dots,A_N\) in bitsets and search all pairs \((i,j)\) exhaustively and count the number of \(1\)’s in \(A_i\ \mathrm{AND}\ A_j\) in an \(O(N)\) time (with a constant factor of \(\frac{1}{64}\)) so that the problem is solved in a total of \(\mathrm{O}(N^3)\) time (with a constant factor of \(\frac{1}{64}\)).

Since \(\frac{3000^3}{64}=421875000 \simeq 4 \times 10^8\), this solution is fast enough. We may further halve the execution time by only searching \(i,j\) such that \(i<j\).