Let’s split the entire walk into sections of lengths \(2\). For example, we see \(S \rightarrow T \rightarrow U \rightarrow V \rightarrow S\) as a concatenation of two sections \(S \rightarrow T \rightarrow U\) and \(U \rightarrow V \rightarrow S\). Since C4 is a bipartite graph, we have only \(8\) possible types of sections. We divide them into three categories:

• \(T\)-crossing types: \(S \rightarrow T \rightarrow U\) and \(U \rightarrow T \rightarrow S\).
• \(V\)-crossing types: \(S \rightarrow V \rightarrow U\) and \(U \rightarrow V \rightarrow S\).
• Returning types: \(S \rightarrow T \rightarrow S\), \(S \rightarrow V \rightarrow S\), \(U \rightarrow T \rightarrow U\), and \(U \rightarrow V \rightarrow U\).

Let’s fix the number of \(T\)-crossing sections (call it \(i\)) and \(V\)-crossing sections (call it \(j\)). Then, the total number of valid walks is the product of the following values:

(Here we denote \(C(x, y) := \binom{x+y}{x}\), the number of ways to arrange \(x\) items and \(y\) items. Define \(C(x, y, z)\) similarly. Assume that it is zero for invalid indices)

• First let’s choose the types and relative orders of \(T\)-crossing sections and \(V\)-crossing sections. There are \(C(i, j)\) ways to do so.
• Then, insert returning sections of types \(S \rightarrow T \rightarrow S\) and \(S \rightarrow V \rightarrow S\). There are \(C(\frac{i+j}{2}, \frac{a-i}{2}, \frac{d-j}{2})\) ways.
• Then, insert returning sections of the two other types. There are \(C(\frac{i+j}{2} - 1, \frac{b-i}{2}, \frac{c-j}{2})\) ways.

Therefore, the answer is

\(\sum_{i,j} C(i, j) C(\frac{i+j}{2}, \frac{a-i}{2}, \frac{d-j}{2}) C(\frac{i+j}{2} - 1, \frac{b-i}{2}, \frac{c-j}{2})\).

This is equal to:

\((\frac{a+d}{2})! (\frac{b+c}{2}-1)! \sum_{i,j} \frac{(i+j)!}{((i+j)/2)!((i+j)/2+1)!} \cdot \frac{1}{i!((a-i)/2)!((b-i)/2)!} \cdot \frac{1}{j!((c-j)/2)!((d-j)/2)!}\)

and this is FFT-friendly!