The problem can be reframed as counting the number of strings of \(N\) tokens X+, X-, Y+, Y-, Z+, Z-, such that \(\text{count}_s(\texttt{X+}) - \text{count}_s(\texttt{X-}) = X\), and likewise for \(Y\) and \(Z\).

First, let’s assign \(X \leftarrow |X|\), \(Y \leftarrow |Y|\), \(Z \leftarrow |Z|\), as this doesn’t affect the answer. (It’s equivalent to swapping X+ for X-, etc.)

And we consider the case that \(X + Y + Z > N\) or \((N-(X + Y + Z)) \text{ mod } 2 = 1\), where the answer is \(0\).

First let’s consider a reduction of this problem to two dimensions (i.e. omitting the Z+ and Z- tokens) for a string of length \(X + Y + 2k\). The answer would be

\[\binom{X + Y + 2k}{k}\sum_{i=0}^k\binom{X + Y + k}{X + k - i}\binom{k}{i} = \binom{X + Y + 2k}{k}\binom{X + Y + 2k}{X + k}\]

The left hand expression can be interpreted as first picking \(k\) tokens to be negative, then picking \(X+k-i\) positives to be X+ and \(i\) negatives to be Y- (thus leaving \(k - i\) instances of X-). We can then apply Vandermonde’s identity: \(\displaystyle\sum_{i=0}^c\binom{a}{c-i}\binom{b}{i} =\binom{a+b}{c} \), this can be interpreted as drawing \(i\) balls from a bucket with \(b\) balls and drawing \(c-i\) balls from a bucket of \(a\) balls, which is bijectively equivalent to drawing \(c\) balls from the combined bucket of \(a+b\) balls.

We’re now able to calculate the two dimensional case in \(O(1)\), ignoring precalculation of factorials and inverses. It is thus relatively easy to solve the three dimensional case in \(O(N)\), by fixing the number of Z+ and Z- in our string and summing the cases.

\[d := \frac{N - (X + Y + Z)}{2}\]

\[ans := \sum_{k = 0}^{d}\binom{N}{Z+2(d-k)}\binom{Z+2(d-k)}{d-k}\binom{X + Y + 2k}{k}\binom{X + Y + 2k}{X + k}\]