The large value of \(N\) makes it impossible to try all possible quadruples \((a,b,c,d)\). Let us first consider the following easier version of the problem:

• Given integers \(N\) and \(K\), find the number \(f(N,K)\) of pairs of integers \((a,b)\) such that \(1 \leq a,b \leq N\) and \(a+b = K\).

We can find it with a simple formula; actually, we have \(f(N,K)=\min(K-1,2N+1-K)\) for \(K=2,3,\ldots,2N\). For example, the distribution of sums when roling \(2\) dice is \(1,2,3,4,5,6,5,4,3,2,1\) for \(K=2,..,12\).

Let us get back to the original problem. We can rephrase the condition as \((a+b) - (c+d) = K\), so let us first fix \(x = a+b\). Then, we can rewrite the condition as “\(a+b = x\) and \(c+d = x-K\)”, so this case contributes \(f(N,x) \times f(N,x-K)\) to the answer. Thus, we can find the answer by summing this value over \(x = 2,..,2N\).

The time complexity of this solution is \(O(N)\).

By the way, we can also solve this problem in \(O(1)\) using the inclusion-exclusion principle and so on.